N=1000;
H=[-8159166,-7278249,-6638549,-5827264,-5907312,-5050912,-4839331,-4830138,-4349788,-4092278,-4051035,-3873194,-3895656,-3490511,-3137869,-2415933,-2313421,-2161568,-1493916,-1128050,-302872,-99316,-18053104,-18084152,-17562178,-17053937,-16192805,-15369394,-14698440,-13812371,-13179723,-13157563,-12967609,-12410773,-12476731,-12190345,-11646806,-11044084,-10336223,-10017571,-9750837,-9135172,-8721911,-8748133,-28198631,-27541410,-27614673,-27138571,-26305578,-25829896,-25765810,-25523342,-24889204,-24080507,-23748668,-22903943,-22499854,-22015681,-21820897,-21340229,-21031508,-20595124,-19812073,-19491437,-19241913,-18613507,-40294069,-39907036,-39043999,-38571961,-37788284,-37302232,-36815766,-36301061,-35834587,-35108235,-34451472,-33879657,-33226956,-32462924,-32555761,-31790535,-31267936,-30534025,-29911796,-29692951,-28920058,-28638402,-49604610,-49108233,-48243090,-48115401,-47272920,-47042612,-46803233,-46691365,-46151924,-45527565,-45241866,-44467433,-44211204,-43849534,-43153126,-43236748,-42505227,-41606535,-41498143,-41529043,-41558811,-41099896,-59879259,-59036753,-58262769,-57860360,-57649879,-57094887,-56364949,-56313039,-55892357,-55506127,-55194632,-54580187,-54416580,-53672070,-52931861,-52649845,-52145097,-51779228,-51093528,-50822901,-50493978,-50249781,-67988192,-67822152,-67060747,-66987878,-66461967,-66237459,-65844648,-65126961,-65123193,-64785251,-64731271,-64258444,-63783279,-63752515,-63029409,-62206990,-61843286,-61213463,-60806919,-60148197,-60236263,-60215253,-78300225,-77803951,-77330808,-76910648,-76458778,-76012860,-75439500,-74907794,-74238772,-74009324,-73172528,-72966610,-72653713,-71986140,-71672336,-70975396,-70209993,-70050306,-69513966,-69267972,-68582534,-68228774,-87238636,-86524386,-86110280,-85682983,-84994558,-84372653,-84332567,-84326905,-83811891,-83473285,-83247490,-82744950,-82693823,-82045018,-81991334,-81349594,-81323117,-80554165,-80587065,-80414454,-79549530,-79199599,-95270359,-95353439,-95185990,-95101940,-94443065,-93677509,-92786640,-91914939,-91587358,-91188303,-91079837,-91046653,-90950763,-90999937,-90297151,-89999242,-89137759,-88568821,-88356443,-88208068,-87884743,-87845719,-100620384,-100407978,-100085924,-99269217,-98806499,-98508696,-98523726,-98412119,-97930467,-97784142,-97703457,-97115784,-97146365,-96617509,-96621921,-96508692,-96285533,-96250502,-96019172,-95907693,-95341827,-95220015,-110185119,-110094812,-109265152,-108561017,-108595770,-108305855,-107804618,-107366669,-107348494,-106628414,-106192127,-105416997,-105400614,-105397057,-104967958,-104447542,-104323042,-103795460,-102962263,-102249860,-101578484,-101424536,-118269063,-118238277,-117963854,-117150010,-117151371,-117237563,-116457854,-116286198,-115882975,-115444972,-115024409,-114437935,-114449728,-114120211,-113891272,-113483435,-113087295,-113007101,-112112644,-111566784,-110799809,-110804685,-127343219,-126659834,-126192034,-125501533,-124684155,-124230979,-124172473,-123860639,-123433510,-122575123,-122273688,-122011236,-121452644,-121274807,-121050841,-120630786,-120306231,-120329869,-120256872,-119693987,-119576503,-118753548,-135380163,-135060206,-134483978,-134259761,-134300512,-133635481,-133621681,-133074712,-132712082,-132062181,-131406458,-130874676,-130903737,-130709423,-130116208,-129683885,-129187338,-129065130,-128763058,-128369791,-128054734,-128082715,-145014268,-144308121,-143796278,-143766018,-143497257,-142783797,-142151660,-141439066,-140614743,-140015031,-139961274,-139434342,-138739033,-138369104,-137866143,-137549729,-137362904,-136943108,-136943083,-136350296,-135984782,-135562475,-153262991,-152849849,-152331893,-151863642,-151924319,-151504199,-151258886,-151249557,-151091068,-150763727,-150572707,-150315567,-150225513,-149327058,-148457210,-148078004,-147617919,-147162406,-147030032,-146589638,-145701998,-145462455,-161715201,-160880571,-160884454,-160929837,-160937104,-160084252,-159195922,-158317638,-158215473,-157862325,-157467354,-157217976,-156919196,-156777884,-156765920,-156014946,-155680350,-155387001,-155333465,-155112693,-154535829,-153918088,-170574582,-170452937,-169594043,-169579612,-168874710,-168791341,-168512814,-167808279,-167136752,-166955289,-166717195,-166769744,-166646761,-166610992,-165724517,-164918776,-164722817,-163830830,-163738787,-163405652,-162643529,-162494305,-179267667,-178687529,-177903716,-177520934,-176654083,-176608131,-176589216,-175710321,-175785932,-175501470,-175331441,-175383341,-175312777,-174882736,-174301594,-173862813,-173884842,-173281351,-173126327,-172854808,-172122035,-171396933,-187653843,-187071570,-186617049,-185969836,-185639333,-185425603,-184855209,-184757079,-184853904,-184650748,-184494390,-184340692,-184232864,-183617670,-182744694,-181979896,-181391416,-181441282,-181498742,-181177643,-180469067,-179918239,-193625117,-193677446,-193487484,-192801045,-192263217,-192076498,-191764774,-191200515,-191063961,-191126554,-191116816,-191029103,-190918931,-190483000,-190039075,-189825856,-188971763,-188829663,-188482334,-187888562,-187920482,-187814483,-199796056,-199066223,-198592224,-197955157,-198015688,-197357464,-197301972,-197038581,-197106902,-196640532,-196262251,-196131011,-195775601,-194966446,-194633279,-194452309,0,815431,1009136,1892613,2295505,2684109,3497732,4043496,4227869,4925302,5161704,5236337,5213489,5648058,6064208,6393121,6556845,6789608,7201929,7421073,7853574,8088865,8110832,8352876,9232196,9805914,10011000,10131314,10992388,11411230,11955240,11936694,12246197,13097416,13601368,13641567,14014877,14348747,14514362,15189802,15821973,16683245,17441870,17994789,18892488,18882375,19353837,19915445,20375288,21235399,22022783,22330705,22416313,22376494,23021509,23624965,23594868,23845906,24110159,24818671,25327908,25707484,25846726,25786309,26139164,26297355,26331236,26861581,27162559,27365615,27754166,28539618,28965445,29075310,29386016,29721334,30103549,30953027,31050073,31875722,32315205,32993081,33807338,34022071,34065747,34339443,34393587,34826280,35227695,35421799,36108261,36418396,37007029,37250653,37662152,38172584,38696343,38630964,38884726,39433075,39833625,40219485,40428829,40892471,41284946,41734365,42069632,42778821,43299376,44188302,44530678,45043137,45230388,46020702,46818665,46986914,47798706,48232206,48722135,49100978,49550866,50118004,50546068,50829972,51013906,51479290,52309511,53170490,53754178,54159325,54955881,55540010,56067845,55988654,56834249,57542914,57580054,58460755,58855241,59473839,59963776,60039814,60300768,60664886,60834211,61158484,61530714,61478256,62242166,62688735,63049747,62975813,63754494,63803739,63985598,64324215,64637851,64814676,65034852,65768410,65707964,66317415,67061022,67216533,67304998,67917764,68521498,69373154,69456689,69736306,69956379,69859155,70201034,70519818,70842744,71390410,72057394,72409019,72382876,72742400,72885245,73586500,74177796,74130495,74575251,75156092,75836419,76123174,76540081,76596557,77133825,77685675,77907368,77842995,78703223,78903188,79556957,79543746,80337524,80550909,81363399,82042973,81969627,82114966,82242293,82669888,83088227,83445218,84111749,84209335,84221205,84760248,85438125,86025251,85932176,86323268,86495028,87079290,87018246,87537604,87629559,87642374,88412159,88666639,89438504,89501604,89761749,90160970,90528523,90698183,91485815,91961010,92624505,92935476,93115687,93431893,93685724,93831299,94492475,94834072,95566520,95746852,95927328,96089203,96350561,97105303,97756754,98427952,98569789,98695090,99095140,99775407,100651915,101250206,102118973,102542563,103025242,103246809,103916568,104383957,105054031,105189108,105861058,105922463,106768995,107588245,108005727,107911858,108072355,108289719,108428710,109158098,109271408,110003430,110372897,110610325,111326396,112045444,111951982,112677543,112953618,113000262,113757951,114147975,114227085,114751413,115059932,115834057,116365534,116685232,117315038,118105365,118203658,118798248,118813173,119171558,119650280,119730594,120035235,120046924,120557543,121305465,122205439,122150315,122431687,123218137,123594803,123680953,123680859,124008581,123991743,124292932,124694286,125240338,125305523,125308073,125638170,125883625,126344120,126943006,127011090,127593097,128263111,128509160,129273624,129663745,129851055,129903653,130547815,130615098,130538580,131365764,131557387,132322347,132900522,133793926,134366050,134519265,134960764,135448389,136028387,136381120,136830570,137489452,137545238,137880443,138285349,138680762,138749847,138933085,138956853,138984004,139515864,140176004,140987444,141339825,141644061,142265250,143088017,143099132,143362622,144012986,144854669,145473908,146346983,146622567,146910016,147455742,148110299,148205912,148403797,148395794,148936557,149058638,149576458,150153850,150406661,151176348,151810224,152540886,153342112,154167342,154181808,155020826,155541519,155806210,155882180,155928973,156501878,156697447,156831673,157364555,158238863,159041286,159832308,160217988,160239461,160459158,161088233,161349370,161831512,161801060,161757539,162037829,162233373,162258771,162239170,162491730,163376511,163910042,164552505,164887328,165558168,166216512,166670157,167352770,168214425,168229347,168418968,169041887,169149703,169231798,169855307,169957812,170289466,171137213,171405734,171410512,171552031,171631954,172479489,172489174,173015543,173633379,174175622,174789246,175123157,175251825,175334132,176212884,176927140,177554963,178072670,178218807,178500254,178959728,178869225,179299482,180065237,180135048,180499921,181360326,181867373,182345322,182269731,182960405,183198943,183859966,184417732,185023225,184986104,185591614,186458473,186959283,187635224,188354165,188811805,188807004,188814259,189542726,190000190,190236191,191028243,191633831,192488639,192399291,193242002,193346271,193519909,193447492,193638243,194106959,194310094,194520803,195086410,195344679,195271526,195540050,196186784,196337133,196399856,196979744,197871632,197991353,198048962,198371122,198450523,198631354,198579464,199040959];
X0=1000000000;
M=9999;
S=[439,701,766,998,491,377,269,893,838,900,573,557,610,816,765,77,718,116,541,590,723,73,838,806,727,830,743,487,796,74,152,248,201,688,105,457,118,445,962,475,44,379,932,869,26,329,710,383,632,895,760,201,558,173,267,404,701,428,37,558,436,699,88,73,243,322,260,597,682,26,55,752,58,41,387,804,402,737,287,64,450,929,595,876,658,962,816,889,163,986,844,846,508,627,281,179,581,156,55,368,438,470,164,950,40,744,730,580,570,58,384,138,860,340,350,200,294,486,709,598,601,513,563,381,196,988,930,228,663,567,993,924,450,426,641,235,486,654,577,963,778,698,345,259,366,350,657,571,138,651,577,948,935,655,106,461,980,44,491,6,153,801,612,767,118,351,86,633,548,612,296,498,810,690,922,868,256,937,300,735,246,247,150,145,13,926,513,212,836,637,636,167,51,420,319,626,66,291,75,198,586,451,127,626,962,859,731,286,258,283,623,714,954,131,219,119,547,836,384,723,259,693,917,249,461,438,298,374,710,168,200,667,176,761,37,953,153,211,891,367,68,749,442,526,958,744,128,364,265,786,39,299,883,189,430,802,167,409,285,793,570,292,389,329,941,808,524,873,593,52,852,977,645,824,877,313,730,748,861,122,670,721,494,26,579,662,911,355,648,299,160,189,14,216,82,422,923,78,515,88,697,292,333,498,15,690,520,324,150,505,954,311,820,271,477,546,803,54,576,349,946,725,275,216,850,589,838,340,889,725,394,767,217,556,350,643,225,613,426,280,834,557,463,884,770,950,244,65,787,103,425,766,428,56,838,259,830,593,483,673,455,19,369,943,969,437,735,133,219,295,181,51,614,497,228,138,88,596,731,769,283,727,954,856,126,322,313,423,466,574,24,182,813,689,464,278,89,869,464,190,869,617,256,519,41,686,825,527,6,203,233,456,347,679,186,241,200,349,700,10,277,90,429,692,19,440,615,262,937,982,481,544,671,700,811,426,61,610,166,661,996,873,592,623,659,24,99,570,18,759,303,670,809,118,858,17,57,166,214,621,1,86,386,761,65,902,422,245,425,423,195,242,674,503,751,775,995,680,812,396,12,665,50,969,845,555,943,359,983,925,861,117,585,622,459,243,459,817,305,801,901,691,527,423,784,382,102,390,531,489,93,837,670,804,60,325,41,663,36,500,725,811,540,892,609,335,4,132,661,123,180,228,897,256,564,629,6,300,133,862,483,193,830,855,928,110,511,656,205,188,361,530,139,937,203,179,329,615,117,301,879,782,783,280,461,900,137,722,68,739,76,989,659,706,71,784,178,97,586,659,625,640,982,287,881,144,42,403,320,672,230,959,489,200,458,843,57,552,510,272,602,393,611,444,226,986,880,274,12,987,245,311,125,245,299,940,359,462,456,810,432,344,862,384,875,930,749,455,229,245,611,229,439,87,714,268,346,962,369,643,525,606,160,410,481,441,600,514,340,693,511,562,40,337,879,282,340,853,16,802,473,225,976,266,733,814,1,995,514,667,138,476,743,568,179,398,829,285,677,503,130,35,758,713,128,433,336,379,534,495,106,21,885,942,573,712,179,44,648,99,250,939,819,518,833,66,646,817,521,106,937,997,80,521,125,256,488,329,641,276,264,490,389,73,25,506,178,333,441,699,15,882,402,252,492,471,563,189,25,988,701,910,790,82,822,72,436,392,176,426,42,662,378,188,936,236,413,406,471,259,503,841,398,778,50,412,541,657,293,791,316,576,480,811,515,831,220,846,323,631,152,834,731,295,356,390,675,64,696,827,948,920,829,848,156,561,722,724,517,282,175,890,23,323,228,87,592,541,738,765,474,335,456,771,940,401,966,841,342,395,884,263,577,334,515,78,163,152,2,325,950,331,337,332,866,935,600,35,997,106,168,467,521,918,840,619,749,666,904,11,457,406,920,900,390,291,633,812,138,832,194,725,591,613,987,310,293,850,12,728,602,792,462,642,32,317,992,883,342,404,282,670,708,58,676,176,778,192,383,107,9,591,90,934,520,398,645,489,839,878,952,484,343,877,28,992,623,37,616,964,31,341,780,280,167,205,640,860,583,934,493,769,832,927,978,526,57,168,23,571,722,961,820,257,284,842,730,126,198,420,960,620,352,374,78,778,794,73,156,529,652,683,363,280,247,478,201,967,354,817,929,862,285,684,192,829,209,648,824,405,636,612,231,637,424,344,200,221,613,868,920,925,985,913,209,478,806,685,841,695,139,26,803,776,104,232,484,882,30,773,630,547,715,163,735,853,225,817,457,55,928,671,124,578,342,150,150,756,397,997,993,607,628,676,628,939,27,235,656,118,291,459,939,42,370,667,295,102,10,91,59,50,107,539,128,790,587,891,292,555,924,524,825,944,701,237,270,597,398,663,548,514,327,776,849,752,185,682,551,222,987,428,773,60,437,478,900,723,984,9,890,857,595,860,985,104,534,359,656,871,9,506,504,255,500,318,455,574,1000,305,39,630,172,341,295,351,648,138,880,543,413,806,960,680,962,43,89,1,879,168,258,602,268,837,732,163,641,451,5,309,575,641,583,591,629,823,393,241,635,725,892,283,722,452,294,726,601,842,937,393,576,154,500,572,583,881,583,952,806,96,11,155,126,776,495,751,246,696,411,411,54,321,295,856,487,833,988,508,383,346,313,449,696,827,694,447,330,628,171,812,723,342,529,146,469,576,871,712,663,42,101,262,25,188,107,316,996,295,674,947,238,969,217,10,201,220,512,49,989,664,359,752,648,891,783,200,676,407,695,776,368,243,335,264,36,727,15,977,425,692,240,641,221,265,673,954,754,462,970,803,439,443,267,365,37,625,733,151,195,190,591,920,921,692,177,891,543,27,571,717,117,97,878,968,116,216,409,707,11,623,708,54,226,615,911,913,66,758,627,765,138,110,967,921,490,574,691,637,26,78,719,721,130,119,52,326,411,648,153,227,372,305,782,504,37,226,835,806,839,539,545,739,161,293,135,505,867,655,29,143,125,466,403,214,783,780,234,845,850,591,968,411,645,218,16,859,416,5,375,210,740,457,871,418,303,333,686,738,147,209,463,330,296,125,199,482,788,58,216,227,321,78,544,636,758,635,201,189,339,17,515,102,553,334,4,176,982,604,374,882,44,922,376,532,331,320,795,159,497,639,405,577,728,486,384,52,183,37,323,423,422,100,183,587,678,956,626,583,301,484,430,315,653,212,74,71,190,660,527,819,550,996,11,776,575,205,904,373,448,646,429,386,233,648,915,103,690,809,424,365,668,219,158,259,510,189,812,369,976,503,203,72,251,66,281,294,718,293,760,981,577,488,63,972,100,427,495,868,151,295,134,683,547,986,502,907,607,246,318,172,715,355,39,524,696,911,759,893,909,4,992,718,762,769,241,519,647,854,219,568,172,772,996,914,930,418,310,852,368,200,88,694,662,694,738,824,253,453,981,819,899,371,120,70,882,771,795,657,66,474,774,677,969,745,474,896,297,273,702,940,897,121,42,560,913,682,470,845,226,178,483,1,634,299,8,382,203,44,645,604,629,509,314,129,174,39,112,223,432,297,358,645,602,43,732,627,780,677,546,233,23,583,481,376,689,690,80,831,724,485,271,486,120,33,670,981,75,124,254,461,207,848,574,109,747,108,790,565,719,312,254,62,987,29,343,782,272,522,568,335,565,103,601,936,482,308,498,42,280,266,532,675,654,567,326,45,948,469,616,72,714,956,802,722,88,58,445,213,639,1,64,640,990,408,667,963,525,151,78,286,845,975,410,170,741,583,294,262,997,631,130,890,533,199,310,174,389,320,635,643,958,217,168,752,215,434,365,141,576,379,66,691,394,948,120,728,580,254,645,102,718,416,780,748,464,979,506,691,50,133,817,466,541,584,903,616,584,443,583,568,963,390,790,247,815,666,446,951,418,438,901,175,958,506,678,903,843,422,254,999,455,571,342,480,124,415,87,289,537,236,768,298,14,522,426,507,260,751,931,781,57,573,525,47,911,203,591,985,310,849,642,92,452,64,956,390,555,15,359,921,586,550,42,900,433,749,374,112,361,797,849,452,864,876,861,927,504,541,641,788,328,149,190,712,193,469,370,133,250,358,831,794,483,95,804,639,532,761,922,652,141,698,71,634,95,364,773,896,745,678,803,270,595,184,410,836,854,587,280,67,841,686,487,34,292,473,246,641,655,404,998,585,2,904,125,664,406,659,677,776,850,207,605,1000,958,756,510,505,587,968,646,298,192,493,791,331,573,506,736,356,306,911,329,877,119,509,987,575,701,659,533,465,819,505,247,259,257,7,65,253,24,606,676,488,326,284,199,899,189,555,946,798,117,691,741,242,972,154,817,53,668,610,125,953,636,66,153,661,652,226,61,266,581,611,786,462,605,732,23,427,526,221,932,537,936,662,265,950,489,872,111,548,947,730,389,762,125,996,715,224,311,318,401,574,10,64,880,421,724,611,935,84,527,134,294,755,531,282,573,554,678,5,253,418,842,145,229,482,326,341,429,42,586,801,541,3,950,214,990,419,203,611,343,220,576,96,824,277,477,765,601,607,851,731,651,768,665,256,669,634,47,942,927,205,69,837,449,591,947,779,556,402,170,378,199,413,97,153,258,336,432,32,365,3,952,488,185,271,200,824,917,843,880,448,561,31,344,208,565,27,880,793,746,232,929,609,486,301,954,883,604,738,595,980,865,432,461,557,703,13,494,399,452,603,752,521,3,73,707,892,9,176,749,846,48,286,288,169,614,397,499,132,958,861,678,215,717,764,570,355,636,540,765,7,644,276,481,467,324,108,702,775,925,404,18,348,229,749,831,720,78,622,740,205,263,231,905,483,441,48,975,816,450,730,500,46,108,460,218,212,358,782,769,66,201,753,223,449,843,827,174,8,302,654,125,863,425,889,100,902,765,397,267,814,56,233,235,933,116,364,803,678,472,609,931,222,13,357,252,390,569,202,877,543,942,743,422,696,187,700,935,778,809,665,216,955,70,191,802,469,292,501,348,351,522,867,358,57,705,753,641,916,943,536,300,543,766,855,191,122,941,102,490,141,165,62,173,832,796,813,945,860,756,341,661,864,148,669,169,149,988,934,646,345,605,903,315,774,462,407,775,203,87,185,973,792,976,610,450,206,10,468,16,52,780,958,918,210,366,328,844,824,480,314,179,223,947,197,953,957,462,392,256,380,105,75,24,804,652,190,279,899,784,154,359,83,980,990,943,795,144,10,359,907,740,351,304,508,89,491,704,125,190,648,553,390,931,557,755,831,736,739,556,857,118,881,990,595,620,839,584,141,34,77,490,527,472,763,709,497,207,42,503,332,958,865,898,55,869,848,181,339,500,303,281,118,340,199,325,946,436,263,553,22,76,999,741,154,108,408,169,743,781,688,878,716,758,217,907,737,87,402,664,542,40,572,470,996,690,949,596,921,484,47,218,31,694,562,248,614,688,508,910,28,307,215,741,811,566,666,548,658,833,853,299,377,756,224,627,889,592,948,291,929,780,512,571,777,984,556,467,145,892,808,707,514,177,821,652,762,117,202,861,908,219,223,190,421,384,541,576,814,422,994,625,928,579,144,75,130,426,902,318,285,728,93,864,271,135,619,843,122,565,450,726,501,884,418,513,232,884,537,261,4,59,177,384,696,251,265,484,316,163,265,145,656,596,769,533,444,316,482,626,97,405,563,831,190,846,996,652,884,984,165,202,937,857,951,47,519,187,769,181,405,389,715,548,75,40,6,834,298,50,864,553,729,565,371,192,880,776,262,487,503,100,538,470,239,255,101,350,310,395,265,398,158,327,518,830,327,884,10,791,959,400,47,512,360,5,388,449,865,890,209,946,162,768,582,811,828,941,92,517,462,427,2,151,920,361,848,401,322,432,366,388,629,430,157,79,944,685,164,562,467,396,195,469,622,156,3,632,945,307,826,324,717,155,730,752,113,795,490,124,926,979,435,57,778,588,596,117,535,173,636,298,756,70,774,288,273,607,871,453,367,177,25,883,437,19,891,217,163,749,405,727,761,311,839,454,328,930,618,420,142,797,69,891,29,400,488,315,341,467,275,378,300,991,487,314,188,35,803,530,652,431,959,874,972,195,324,323,885,384,312,723,406,69,101,724,87,698,714,646,800,487,944,519,834,701,286,417,795,171,571,907,614,649,98,493,344,719,592,247,922,294,999,682,805,293,14,517,616,988,701,736,220,91,204,220,191,291,444,944,571,595,252,948,967,811,284,608,459,403,869,684,448,60,653,97,389,757,246,158,938,862,31,411,847,815,729,889,309,673,402,567,66,691,252,741,368,613,70,547,487,759,185,617,301,938,596,216,956,253,287,287,579,608,898,206,106,987,181,254,482,655,305,598,794,354,165,589,970,231,625,158,482,995,165,46,131,232,466,519,3,84,383,640,204,306,668,433,478,127,690,971,303,485,127,764,593,530,365,110,859,656,75,361,157,455,570,179,984,229,472,46,267,676,887,41,518,435,607,588,873,299,902,816,837,802,382,107,593,74,982,479,453,866,510,292,625,819,798,472,301,787,319,621,954,820,216,698,71,725,729,503,461,143,554,501,194,256,884,106,144,618,606,480,782,444,496,662,436,735,955,269,971,81,477,692,306,684,672,251,761,199,579,674,176,587,855,289,872,654,626,761,167,450,14,753,815,38,331,281,720,339,231,906,760,927,732,659,313,412,841,44,986,185,926,101,371,943,755,198,45,652,793,72,151,978,967,602,585,208,357,860,699,383,803,599,542,613,914,386,649,548,65,77,636,251,848,120,927,170,136,435,114,482,263,663,190,410,439,411,682,954,7,479,935,634,128,460,3,99,752,864,352,596,233,485,957,749,595,563,66,574,412,872,400,784,918,54,334,226,1000,132,828,44,914,418,426,214,700,697,697,793,487,615,151,484,690,910,766,407,21,318,630,562,728,677,741,582,708,853,181,738,704,77,461,478,964,85,797,266,105,894,414,903,957,454,135,460,578,471,808,825,583,81,281,422,93,682,323,996,419,404,212,450,496,366,799,112,271,728,409,870,301,794,731,581,716,77,142,868,643,832,57,963,82,659,125,882,865,671,728,898,793,763,148,922,65,463,296,274,153,755,660,818,793,191,793,467,586,980,574,596,763,449,731,645,700,358,616,870,214,124,317,72,759,50,115,418,273,792,601,204,467,758,784,454,366,84,398,297,633,123,237,371,715,98,652,703,639,625,267,194,594,745,603,286,62,912,747,833,778,944,147,942,230,145,299,874,202,689,932,823,679,858,708,387,740,99,621,193,737,684,111,174,759,614,192,427,20,991,738,177,522,985,756,367,192,492,694,502,759,110,257,228,653,217,460,147,524,132,535,322,779,503,738,314,227,851,526,169,283,246,490,521,259,330,974,257,27,583,98,666,451,739,390,530,52,496,99,731,5,309,368,892,798,346,862,534,951,55,931,431,497,173,241,57,907,523,543,259,917,57,773,766,712,744,636,576,578,311,547,435,925,838,66,174,240,165,985,914,172,476,409,949,783,36,24,385,171,676,688,85,336,884,17,538,12,669,521,638,801,110,978,995,446,919,571,736,659,928,380,110,96,361,926,803,350,587,568,385,988,221,98,239,626,63,668,21,1000,10,775,132,335,173,65,795,366,919,565,226,933,43,832,961,925,118,75,289,844,674,47,1,444,318,243,969,140,858,296,593,245,503,348,930,621,939,257,627,934,976,174,52,128,702,739,725,129,531,81,279,467,729,287,49,917,703,861,491,311,477,147,333,417,68,450,48,428,850,856,27,983,585,839,734,954,409,31,361,69,624,814,77,465,16,622,937,509,104,310,237,729,976,846,569,942,433,935,966,362,25,744,187,127,10,121,808,588,755,914,365,586,261,868,939,111,399,685,441,45,105,991,55,812,859,882,109,162,621,4,484,129,480,431,531,408,923,306,42,487,590,149,289,286,522,577,497,38,422,717,601,574,218,9,529,438,142,189,897,822,986,114,698,511,159,815,59,784,60,516,940,489,953,425,421,835,167,614,671,564,117,340,952,342,371,362,443,592,385,609,581,27,855,487,888,302,678,198,826,592,357,189,790,492,916,748,945,911,684,140,5,643,315,164,864,871,291,148,413,99,452,596,265,79,644,885,533,748,245,237,498,769,206,398,575,702,215,16,533,627,201,337,802,657,402,355,776,735,308,461,958,837,631,855,733,660,409,554,843,746,332,741,210,809,543,936,17,472,818,507,529,16,726,159,776,760,785,538,112,679,941,215,272,256,450,355,49,800,14,671,225,113,771,100,666,642,184,817,99,851,13,583,685,12,906,332,414,46,376,194,8,248,294,576,506,546,836,110,413,957,307,813,295,711,642,444,978,778,369,91,693,141,680,618,97,449,959,674,164,28,431,401,808,768,983,1,452,228,103,554,1,849,440,234,125,142,353,267,722,483,754,772,911,856,27,109,52,821,36,471,842,467,774,697,96,241,192,995,998,399,618,5,492,53,69,240,163,92,423,74,210,555,434,5,769,546,398,985,264,490,769,860,984,513,565,472,976,185,921,380,288,585,93,57,864,210,426,765,617,938,22,922,322,491,11,895,579,949,201,780,868,422,702,898,70,976,892,280,104,186,954,342,826,532,872,348,460,598,735,258,839,849,269,817,906,796,252,800,13,943,28,232,752,810,723,71,988,238,187,943,736,26,203,199,148,158,475,239,960,443,587,120,397,511,604,681,2,828,653,426,87,697,518,915,924,23,8,645,738,716,42,774,504,490,620,792,838,161,422,243,12,487,640,725,619,350,395,272,674,317,758,707,641,372,361,342,504,499,301,634,296,939,857,998,616,891,253,994,968,859,945,334,944,939,453,435,817,804,562,752,58,285,871,197,867,774,324,866,996,384,98,255,590,537,119,781,95,355,37,259,922,381,164,178,124,360,514,336,471,290,305,999,761,541,456,110,141,521,55,805,360,284,263,869,580,496,198,61,615,628,166,621,643,992,63,261,960,340,71,206,116,377,208,758,649,742,905,23,654,131,34,41,572,776,876,370,1,118,117,444,423,220,767,550,173,146,674,616,36,897,236,923,66,887,487,542,489,670,778,905,424,381,365,660,832,709,377,24,767,589,868,763,887,724,264,352,719,829,916,412,224,861,801,136,912,366,46,765,457,591,219,210,818,768,704,256,20,729,77,245,669,979,619,803,263,221,65,953,137,959,95,639,732,233,398,46,982,132,61,533,953,455,900,52,68,650,187,715,616,910,762,866,499,361,26,210,671,149,946,82,411,33,26,947,816,574,723,843,356,779,356,876,633,607,69,317,94,573,558,302,739,682,815,672,833,200,513,650,351,830,787,612,685,940,373,822,819,802,280,569,458,177,682,403,729,360,461,502,264,663,33,378,199,719,364,405,783,318,904,849,855,694,492,461,399,430,664,625,335,623,285,318,376,423,617,819,929,416,14,736,730,625,996,605,83,99,601,771,413,477,223,81,479,143,853,663,265,777,355,405,427,835,442,347,174,406,24,42,265,233,367,49,268,492,158,521,359,415,534,992,795,187,6,592,815,719,942,240,939,915,214,904,439,128,438,865,404,484,695,250,313,225,288,147,654,334,905,396,387,796,435,806,545,601,853,583,535,167,15,113,285,958,889,524,443,852,139,518,746,19,38,937,297,274,889,436,240,641,300,575,463,192,32,499,711,704,140,647,583,656,144,851,415,432,572,631,839,1000,664,620,928,249,557,904,848,266,298,782,586,883,735,259,563,197,37,464,5,142,986,102,902,944,8,60,449,354,847,571,971,933,29,89,582,463,148,936,928,410,843,791,748,982,618,134,551,449,298,22,978,645,793,150,606,241,985,126,194,693,218,374,871,65,890,975,347,718,59,599,752,819,876,472,357,40,757,658,451,637,311,803,896,43,48,821,166,937,594,583,692,919,509,89,555,86,151,852,953,532,170,439,432,899,805,402,111,922,232,373,223,658,99,849,990,626,55,436,486,137,67,856,358,970,351,173,695,402,924,361,127,571,393,894,352,844,110,275,529,149,731,312,659,598,104,118,12,48,198,260,830,706,60,802,808,876,2,304,603,470,777,839,805,113,240,54,208,828,767,725,779,103,662,972,423,707,293,275,498,174,709,531,750,34,245,219,258,366,765,36,294,979,734,588,659,984,446,869,728,4,127,334,885,66,369,455,690,351,634,721,832,381,356,395,382,507,718,797,324,345,776,71,442,167,531,850,913,782,261,300,744,845,496,599,159,796,4,611,350,835,519,502,94,467,83,458,54,67,423,182,270,235,419,346,934,300,824,695,719,100,548,908,536,821,337,73,513,966,111,230,74,536,540,780,188,162,186,82,518,731,952,792,928,606,566,30,538,832,284,4,285,875,395,883,432,566,554,874,67,561,57,42,974,444,761,569,194,272,761,545,806,476,665,945,586,40,665,913,990,525,257,666,827,153,514,251,840,726,747,596,493,995,156,309,498,425,542,959,256,758,784,960,654,980,562,762,700,635,396,93,490,105,478,119,825,528,953,66,472,175,444,653,159,110,167,440,374,237,963,748,934,421,559,216,773,301,475,548,246,509,759,920,542,405,979,565,47,830,384,457,167,911,381,927,161,688,282,548,138,298,64,761,772,635,429,751,341,429,331,101,512,695,850,660,34,594,344,18,148,788,847,737,415,15,806,464,130,203,325,815,582,390,397,559,841,362,708,191,213,550,804,263,913,746,341,327,542,702,837,471,762,643,166,784,847,176,263,617,52,661,472,891,290,730,506,716,127,832,315,238,101,582,621,816,755,516,927,810,82,315,562,181,240,1,173,824,711,248,72,115,694,55,875,806,206,447,222,106,301,774,810,469,437,934,382,841,421,967,434,798,910,375,623,162,630,112,996,63,991,153,201,4,880,866,38,65,322,939,435,647,211,781,57,541,733,391,351,163,663,833,917,417,234,363,44,984,820,710,507,87,903,305,954,878,874,364,649,589,37,968,616,84,505,355,728,236,165,695,304,116,905,355,208,933,973,144,785,141,506,845,201,134,223,305,482,207,884,591,292,792,665,700,589,690,151,730,7,68,965,88,969,678,163,70,3,64,617,844,542,683,416,11,664,853,111,170,179,712,502,529,591,860,165,912,450,615,269,888,742,915,437,392,138,207,229,176,574,531,29,937,43,768,30,105,287,853,759,466,948,122,88,635,146,711,841,733,991,565,459,999,53,634,525,824,995,113,543,155,761,311,433,13,135,125,908,624,326,876,919,131,141,363,874,270,148,619,101,617,92,778,713,477,100,290,277,993,236,506,497,797,348,394,85,289,820,995,914,742,605,668,167,755,230,933,708,288,391,638,233,750,161,871,351,67,899,801,637,145,589,667,963,655,239,814,441,990,593,680,144,421,148,347,614,652,559,846,742,995,890,257,965,354,350,133,341,802,697,449,36,58,789,861,213,554,706,737,661,610,614,598,446,75,603,490,806,412,472,935,72,269,837,493,289,535,395,386,163,744,712,456,668,770,46,694,790,324,957,900,89,391,99,59,843,481,690,490,894,684,417,713,353,696,216,624,589,419,16,336,272,735,823,896,492,107,959,96,424,967,592,896,221,59,800,928,921,504,537,145,950,477,522,978,163,482,851,276,169,751,180,781,638,901,574,367,876,587,64,561,498,105,50,99,449,928,997,174,647,166,472,377,470,901,947,788,677,212,590,615,21,948,809,779,700,619,845,350,492,259,705,930,52,332,389,407,365,204,690,235,173,445,967,248,702,790,380,53,407,879,209,74,513,984,78,40,186,714,740,582,164,676,330,868,702,910,832,930,65,72,319,201,867,427,734,503,814,446,341,839,873,305,980,54,396,37,603,373,320,16,227,77,532,772,75,677,752,536,187,654,268,101,348,78,593,665,780,711,646,958,493,968,3,308,951,449,632,25,552,555,294,135,26,333,172,53,388,287,130,283,38,209,864,729,313,436,735,904,283,214,678,647,782,817,509,270,738,613,756,653,933,1000,676,125,361,620,124,381,917,616,492,973,81,876,668,710,870,289,853,54,394,118,822,719,463,995,95,480,124,560,120,394,450,190,82,532,336,339,148,885,270,385,790,304,948,208,720,714,498,54,195,317,553,525,262,640,616,516,289,859,271,764,700,70,839,683,336,82,407,715,308,342,63,531,432,410,367,715,188,174,967,204,825,131,976,221,694,384,665,654,683,765,866,255,272,995,836,360,286,744,694,794,276,382,128,740,226,372,922,903,808,795,748,897,175,778,543,620,309,696,874,271,853,56,141,970,268,951,97,774,972,319,964,522,515,743,536,750,596,455,221,250,540,519,209,863,477,656,278,907,109,609,115,376,166,514,232,70,344,107,134,971,561,533,3,921,99,823,889,399,829,921,576,709,592,324,374,572,890,422,237,771,637,921,804,674,744,204,963,281,140,720,755,49,983,68,778,161,283,904,666,377,695,12,699,369,644,920,267,57,432,421,348,850,861,930,389,971,114,295,710,325,1000,692,663,838,237,306,81,792,507,552,419,250,657,206,613,340,776,301,424,583,158,203,59,970,37,474,646,941,876,145,33,232,36,585,484,780,171,752,184,55,75,328,972,859,99,505,288,648,876,401,325,556,996,490,266,1,765,667,95,350,414,820,708,115,216,221,769,385,201,247,927,711,243,961,93,77,557,483,923,115,703,965,682,362,154,544,864,56,349,147,343,808,424,86,815,631,707,786,886,622,135,589,422,694,763,985,654,126,407,149,630,367,371,922,919,447,304,854,247,688,365,683,24,345,538,489,82,162,607,366,355,44,133,812,13,406,875,586,487,80,785,672,393,298,327,630,172,748,566,685,566,207,893,588,97,914,484,867,893,814,187,674,384,257,499,738,52,661,27,66,512,505,299,874,460,581,971,915,264,458,556,315,277,535,317,260,298,468,518,405,711,217,703,863,717,855,713,216,819,700,235,130,649,322,925,509,815,353,839,743,493,807,786,586,580,334,133,693,427,229,272,696,690,516,83,563,738,692,47,839,362,980,331,283,962,380,703,15,898,724,379,227,250,5,432,472,355,814,501,261,108,711,98,2,429,200,855,904,415,353,885,293,137,779,138,771,3,525,481,769,53,768,31,104,39,466,110,751,394,77,596,253,837,848,540,557,384,339,707,588,772,775,667,876,431,419,330,780,699,879,835,860,792,571,715,60,708,840,531,893,297,364,908,54,726,1,893,647,123,639,279,536,673,548,280,930,6,722,82,204,588,704,876,590,155,894,463,609,161,597,273,259,664,652,76,814,231,771,295,705,574,322,355,269,134,722,326,289,269,153,874,116,405,498,54,889,629,458,467,125,30,130,143,130,815,123,4,143,448,20,513,476,225,230,167,265,370,751,44,599,300,97,242,213,678,955,1000,499,392,181,815,417,51,896,413,232,342,579,156,647,193,758,83,606,380,561,563,134,167,741,226,757,67,520,274,781,567,652,738,357,75,881,43,214,912,773,715,359,573,650,684,72,122,15,261,681,199,772,158,882,932,282,24,28,490,976,298,406,704,174,508,880,310,396,630,226,805,539,873,813,835,569,124,1000,234,424,407,19,906,8,698,375,721,55,502,538,145,191,978,350,649,863,102,602,161,935,986,367,626,672,535,147,818,281,404,656,467,546,713,446,413,339,350,211,462,901,732,721,880,111,738,55,458,289,600,429,948,291,454,131,183,581,661,522,625,384,444,537,156,723,107,600,136,87,922,79,779,490,330,487,711,982,706,231,691,762,210,375,487,574,50,688,579,859,35,456,1000,608,308,129,909,253,93,770,538,26,78,492,448,384,856,333,950,221,410,511,348,819,396,666,290,66,414,732,704,360,689,895,327,311,100,818,750,998,655,93,949,749,298,112,445,789,846,60,653,285,786,408,61,549,486,756,829,565,658,336,93,830,375,85,542,998,611,82,775,184,497,623,144,401,926,901,314,562,820,162,75,948,969,104,869,790,728,926,320,705,230,381,898,243,37,267,837,918,675,194,544,561,979,874,259,996,234,457,879,816,881,585,282,820,425,233,494,56,81,609,443,852,410,65,815,201,442,954,604,925,827,411,241,762,740,740,806,720,414,101,412,637,823,463,801,507,17,545,687,929,435,219,774,463,6,542,148,334,320,200,635,245,371,899,986,876,798,526,497,267,674,346,160,531,693,94,856,562,153,577,400,659,237,502,584,747,82,506,113,75,366,359,466,908,275,116,315,645,728,561,556,407,846,302,373,168,67,508,359,226,497,978,633,788,319,120,139,846,134,358,766,57,100,821,825,460,227,492,772,527,938,91,47,130,82,635,458,365,249,738,958,841,185,138,402,429,305,954,118,66,545,667,91,174,698,316,968,395,611,172,156,736,212,534,218,5,597,407,55,771,359,177,637,721,665,19,595,903,651,973,17,5,821,311,312,988,496,546,390,266,315,421,901,41,686,648,69,145,401,347,820,784,301,663,628,360,993,179,748,752,557,111,892,640,457,996,141,361,766,296,941,890,595,229,654,507,640,490,24,668,941,352,785,238,531,846,715,328,761,156,845,226,711,74,151,716,877,344,234,518,916,975,196,225,587,342,319,628,34,813,138,496,873,852,542,203,441,620,986,807,33,76,942,235,881,124,338,279,641,117,590,220,138,77,27,873,323,190,264,438,380,727,749,403,869,577,51,961,919,538,713,238,209,84,871,932,955,375,629,635,485,345,691,961,832,732,826,96,491,767,841,527,254,306,648,926,41,357,568,790,277,993,768,182,769,869,544,710,933,497,648,854,337,237,944,383,830,698,193,735,306,759,130,1,96,132,667,866,797,130,549,843,235,935,998,309,256,669,544,191,271,971,955,218,109,514,37,596,244,760,744,799,842,271,27,530,697,263,118,37,425,254,402,489,136,286,21,533,56,14,521,737,136,598,238,757,337,454,834,897,361,847,655,902,946,512,164,675,115,489,713,953,981,818,471,550,390,708,372,812,120,454,674,954,626,176,577,304,5,147,591,879,551,357,478,182,466,448,885,725,405,691,676,700,33,551,195,116,916,754,571,731,32,638,579,971,116,243,547,684,785,319,676,996,29,668,933,749,362,921,598,30,743,94,399,815,829,147,992,25,290,241,426,819,752,503,460,149,182,893,246,943,789,763,209,794,187,466,148,21,170,825,607,568,417,208,242,403,673,928,613,310,592,871,361,530,608,687,325,702,976,799,193,867,696,328,662,399,33,33,122,740,922,425,511,641,219,243,325,182,252,924,218,956,358,430,856,938,928,648,918,208,866,842,924,966,924,188,379,309,639,991,881,243,674,122,80,810,5,85,480,938,240,784,271,249,300,788,743,817,72,16,127,633,196,564,239,305,264,801,184,898,221,141,312,3,266,282,41,556,239,999,499,429,948,157,540,239,466,851,974,880,144,48,192,51,678,119,506,133,148,5,236,295,451,956,399,530,754,651,538,693,177,690,717,401,488,105,505,820,184,697,629,224,216,857,937,340,968,241,325,608,864,698,937,45,249,66,78,570,674,11,867,471,179,708,520,732,436,526,302,106,830,975,708,407,576,985,282,197,898,907,432,900,540,182,326,258,255,137,325,265,106,508,124,568,861,703,771,447,968,474,603,175,172,142,675,399,599,26,394,119,644,726,459,791,712,618,883,792,909,271,756,768,393,772,413,321,15,369,934,507,372,111,296,124,458,92,297,326,671,10,371,944,333,744,598,786,860,151,376,525,130,405,739,488,345,500,270,91,600,764,545,838,440,779,749,346,671,843,1000,782,671,987,196,994,999,675,217,750,352,275,565,874,856,940,482,111,385,189,247,580,18,822,396,554,164,231,122,967,581,665,455,269,383,315,229,683,33,309,715,825,724,120,378,904,374,802,777,591,937,773,64,726,428,128,695,493,64,988,806,965,915,111,814,612,671,371,534,748,987,80,790,429,456,660,951,957,772,745,872,54,561,166,985,79,102,835,442,48,164,344,171,74,601,966,445,92,327,492,935,878,53,234,497,112,956,552,772,731,722,55,727,998,865,326,282,857,392,213,53,868,711,853,768,599,559,372,492,355,215,860,776,103,927,340,380,900,143,141,761,648,336,21,661,677,137,374,50,538,18,896,624,135,243,297,469,13,989,443,11,299,967,109,625,705,473,375,447,655,851,841,454,278,254,212,908,644,713,767,563,379,804,450,507,347,727,509,402,290,243,401,74,834,799,709,506,562,171,689,242,154,359,606,779,451,532,578,67,756,817,783,620,549,582,468,766,934,715,330,863,520,113,240,985,569,775,861,443,508,933,124,341,30,899,834,807,224,570,25,626,219,929,304,877,486,752,423,472,906,631,790,980,381,951,70,800,961,703,22,708,21,223,462,304,601,303,646,468,414,680,927,985,779,305,360,990,616,794,169,395,853,515,35,889,906,445,164,791,288,999,358,261,894,649,904,763,989,299,155,489,187,966,6,584,570,248,960,767,665,308,236,790,768,527,351,870,360,595,731,341,376,198,991,773,128,515,795,278,960,615,679,878,617,428,508,255,305,720,441,224,762,926,830,977,740,539,204,675,597,192,9,548,303,670,671,710,193,396,213,753,483,259,940,235,398,193,706,70,185,608,393,153,940,511,768,732,687,479,896,136,867,294,536,259,703,950,864,511,539,414,216,300,15,31,512,184,219,391,465,149,280,320,810,458,901,345,243,591,75,155,788,468,728,12,206,314,390,38,200,160,44,544,562,134,146,587,709,453,593,125,119,420,856,480,954,675,95,755,621,538,326,223,329,345,102,658,620,537,629,398,592,809,877,826,109,993,326,679,465,738,702,83,606,155,743,976,795,692,496,637,168,197,849,123,709,358,115,448,547,312,301,526,633,482,743,244,335,860,105,426,349,535,892,265,268,674,766,424,403,340,810,391,130,1000,661,526,474,571,352,390,169,663,44,406,257,707,688,774,497,783,421,454,90,156,17,191,10,760,86,424,675,853,915,249,781,595,352,554,134,152,46,604,824,326,412,142,50,28,530,944,796,858,400,322,582,945,383,573,273,839,141,280,412,398,708,155,407,950,580,318,202,373,907,570,950,261,107,598,906,309,667,434,246,485,323,494,371,478,804,947,567,470,485,336,684,951,446,685,265,1000,591,778,655,138,225,80,52,140,626,982,570,14,476,900,689,496,487,490,719,794,521,593,230,821,340,944,229,552,527,87,524,715,282,830,3,855,62,574,339,59,114,406,555,583,758,830,771,43,58,406,507,479,759,935,548,188,44,832,405,585,233,209,310,14,494,898,488,956,555,876,761,306,441,653,219,864,7,912,53,606,838,546,168,284,68,61,27,931,459,919,669,570,362,187,921,241,465,878,20,601,17,666,104,768,393,21,108,472,153,778,16,937,953,358,580,337,826,162,601,626,858,855,70,795,371,100,587,860,669,594,96,382,534,591,246,983,904,101,236,385,730,779,690,244,668,282,289,750,951,928,823,881,818,695,238,916,365,230,813,399,288,718,613,35,852,501,37,590,583,565,308,706,940,453,565,423,432,534,885,483,524,438,358,544,881,279,431,725,950,576,360,282,820,330,833,343,921,827,779,349,655,917,333,763,429,719,983,841,315,26,746,40,794,636,180,679,913,47,831,998,680,298,66,845,983,238,958,660,951,801,561,724,798,653,981,580,750,217,929,428,215,302,326,301,479,594,971,942,864,919,664,319,913,412,389,552,930,513,266,193,644,607,592,331,454,589,910,245,432,699,420,439,794,921,986,618,613,88,49,948,127,343,192,687,410,398,767,147,742,989,831,54,969,205,630,250,357,597,982,102,945,445,774,42,302,749,271,871,594,478,159,195,871,143,488,488,428,896,298,214,857,489,451,115,367,459,357,33,621,989,439,631,35,111,177,45,721,281,787,540,215,388,198,610,126,623,17,89,461,266,516,401,805,733,775,592,996,833,555,264,548,981,447,8,348,697,699,816,548,909,568,424,205,74,180,841,926,175,217,426,775,796,398,787,712,361,444,373,26,711,681,439,275,645,807,881,437,707,390,411,200,745,68,605,74,424,803,88,973,111,122,179,952,806,761,990,499,397,48,754,279,165,72,518,859,213,472,642,767,101,792,502,227,285,456,106,912,214,193,711,101,623,26,228,706,968,867,409,919,825,61,719,796,819,566,236,906,628,256,690,488,183,2,217,431,921,5,623,269,996,807,582,284,14,410,501,75,602,302,268,354,317,745,12,730,265,981,483,314,836,25,947,746,360,741,572,738,77,769,980,267,97,158,421,307,798,67,174,20,531,40,703,718,985,37,81,399,622,59,50,57,868,745,676,843,18,119,311,357,609,318,177,440,175,28,388,411,806,683,983,126,237,746,970,465,373,234,38,509,844,698,505,600,692,377,301,773,500,162,681,705,61,66,430,589,149,403,403,898,998,540,744,887,319,69,765,517,689,574,538,994,874,736,944,328,964,330,790,830,606,228,124,868,697,374,155,147,675,857,354,466,622,860,361,665,601,79,376,912,549,691,487,743,160,382,247,631,868,194,895,87,8,622,183,632,141,651,416,880,985,632,777,825,990,948,218,290,947,458,875,955,800,247,996,677,430,117,190,335,676,523,232,553,506,793,986,635,368,335,429,734,543,486,231,288,214,21,506,931,53,676,846,487,716,644,673,866,28,363,709,662,308,323,65,818,908,739,405,894,52,708,890,939,589,668,622,832,638,533,747,621,975,94,33,842,288,152,174,360,594,650,196,22,388,708,554,284,574,214,552,610,272,624,847,136,515,875,157,279,142,286,556,62,873,897,323,694,364,692,235,37,624,48,107,469,660,932,99,221,704,40,675,757,508,853,299,878,9,313,92,847,510,734,413,96,715,427,758,889,176,241,264,211,310,726,178,148,28,508,300,222,946,691,150,985,200,225,456,659,671,744,891,430,758,911,142,841,237,630,857,332,148,765,509,168,412,149,825,628,12,261,693,416,572,621,617,780,532,829,917,217,117,662,538,85,765,263,775,835,903,1000,420,472,416,802,450,261,354,523,799,771,787,5,685,561,734,671,20,176,792,930,410,46,899,4,257,53,205,671,680,260,1,595,991,707,860,606,839,947,263,154,102,755,619,662,790,83,607,466,519,683,916,518,959,196,120,755,104,364,733,168,977,589,66,69,258,263,696,922,308,624,869,816,581,554,115,62,855,420,889,588,746,950,960,435,116,641,662,465,863,468,101,512,34,975,948,79,957,106,788,207,456,358,859,47,276,625,891,142,456,397,683,903,468,298,556,879,345,30,196,440,22,51,149,817,467,784,822,474,816,733,488,275,725,851,9,829,315,249,555,607,905,471,69,169,55,325,592,635,558,444,2,438,325,339,37,25,252,690,8,884,875,713,708,840,810,176,183,891,954,784,971,103,698,344,15,75,946,513,411,80,779,649,408,629,891,418,877,561,396,659,474,975,846,132,775,172,839,750,453,322,729,104,731,800,859,90,401,550,413,908,823,588,704,175,694,883,162,169,581,298,701,52,396,969,609,416,699,360,428,987,171,344,912,527,859,816,788,699,51,568,320,215,675,985,125,340,724,137,577,137,309,442,902,462,782,459,172,491,551,613,329,721,393,687,951,183,219,648,5,669,357,67,787,451,503,645,41,913,650,600,880,144,333,411,343,815,464,990,574,239,907,785,678,118,527,157,214,966,867,521,614,950,143,437,822,598,83,794,142,375,456,102,935,200,197,259,664,89,346,880,473,634,79,990,395,964,45,675,693,645,979,249,447,799,753,680,9,906,39,62,627,420,142,837,462,911,957,836,721,82,180,451,940,221,563,930,272,209,851,466,596,453,554,930,816,945,427,682,500,861,259,66,256,186,260,403,389,430,916,28,114,484,638,637,991,785,783,119,501,542,145,176,594,924,250,186,32,954,149,132,855,865,207,383,269,767,489,161,308,838,620,260,475,477,735,608,722,508,587,707,98,84,710,223,329,588,250,763,441,244,254,311,474,988,843,619,930,156,39,240,755,381,852,357,20,566,785,194,325,520,327,175,855,889,892,149,872,323,594,251,482,925,456,577,708,599,839,248,687,554,205,286,218,877,844,885,93,192,691,44,856,83,603,348,931,967,426,27,823,490,866,731,603,406,578,156,575,43,603,876,68,759,51,333,169,244,716,918,582,537,333,983,147,278,175,968,848,116,560,162,198,690,618,452,28,184,276,246,994,790,247,360,425,941,137,59,616,396,948,334,463,539,127,169,22,162,346,125,965,777,214,192,997,513,178,116,437,73,646,128,317,434,250,597,46,226,87,650,766,571,436,462,583,556,593,332,985,301,910,121,626,743,124,503,540,801,106,965,902,763,840,739,568,829,790,425,739,800,29,944,357,554,780,455,408,189,339,726,220,825,306,461,615,124,138,789,403,776,266,973,335,652,362,533,499,656,890,222,464,245,59,494,916,10,324,439,305,631,613,288,231,804,342,738,612,202,16,548,170,951,482,725,512,110,132,776,814,332,230,986,916,58,105,141,603,161,172,232,626,232,623,723,169,840,58,78,937,679,166,522,345,735,690,390,17,631,886,738,857,871,10,582,305,192,567,755,818,81,548,888,499,258,489,197,540,83,646,339,134,228,492,8,312,510,754,438,498,728,808,860,204,651,822,547,766,197,253,330,817,448,123,473,860,627,115,840,823,390,314,303,683,618,418,871,334,614,609,39,386,474,514,887,607,838,498,295,915,51,491,112,960,487,579,553,37,284,245,570,898,562,958,188,184,807,368,501,805,749,409,879,579,339,27,785,986,897,726,532,856,640,16,974,943,751,563,761,878,326,982,317,733,149,946,528,933,405,933,196,276,317,881,480,620,101,349,364,749,581,546,368,493,965,550,357,958,534,307,778,439,279,688,367,168,929,230,548,361,538,427,490,251,148,393,88,181,830,319,958,663,912,38,653,146,899,732,243,21,454,763,562,992,985,698,225,363,396,770,313,118,104,753,896,882,163,945,216,278,423,561,641,690,156,274,537,967,856,386,690,740,29,451,483,921,610,652,580,438,983,390,37,323,629,559,255,713,755,73,761,799,721,147,347,837,327,678,421,52,86,16,128,867,412,883,691,202,852,478,902,145,747,497,546,496,898,149,357,656,706,897,985,232,658,517,101,552,987,337,386,209,763,622,494,41,500,651,139,578,917,64,169,476,174,669,662,133,728,59,260,351,858,665,530,481,724,23,16,627,998,61,334,302,809,660,189,808,707,139,284,35,894,138,259,199,370,481,994,890,861,129,570,374,409,745,986,98,181,649,930,30,793,553,347,547,598,714,467,375,67,411,812,844,856,548,597,561,773,973,191,863,987,471,913,477,680,457,138,715,214,75,949,793,253,733,671,631,587,744,186,662,642,539,861,453,505,542,432,412,337,777,131,708,608,621,919,812,992,321,531,868,488,981,279,900,216,137,259,996,865,310,360,213,986,867,965,438,579,392,274,135,724,709,280,833,549,259,709,459,527,977,507,389,825,903,177,351,900,213,376,945,246,76,39,44,321,938,309,103,844,18,693,770,895,641,268,358,611,841,972,625,383,112,324,925,963,921,620,586,143,169,804,534,340,546,45,331,64,674,350,664,77,459,167,317,163,173,112,755,744,790,82,120,46,192,724,406,300,90,406,629,730,581,969,155,505,87,171,322,56,330,350,617,871,301,985,984,830,97,853,272,950,476,113,831,414,504,741,119,174,412,761,208,558,897,213,272,118,85,202,561,399,242,63,562,64,703,300,147,2,413,761,540,195,954,479,782,733,952,405,656,311,502,83,250,313,157,858,789,908,267,344,960,839,354,295,851,162,689,182,830,365,809,110,585,265,248,381,245,892,552,309,9,376,400,838,381,749,385,86,586,9,233,527,63,806,538,384,428,835,683,409,769,376,693,394,998,998,734,772,444,676,984,878,394,722,986,944,952,440,340,778,439,943,847,37,349,317,250,224,324,421,821,843,812,156,640,567,611,691,796,570,875,155,960,222,507,939,332,874,787,820,464,191,804,484,933,475,668,77,394,888,941,86,63,374,399,7,860,835,208,241,250,961,594,763,200,87,372,213,838,525,6,111,356,163,513,281,323,570,883,52,186,249,374,343,273,880,474,595,936,599,693,718,744,783,857,898,480,695,525,94,248,87,201,330,456,808,61,311,769,560,282,836,930,49,279,25,667,914,980,454,348,492,154,676,86,389,120,873,144,887,118,39,370,946,12,558,780,532,226,596,455,55,41,571,10,938,288,242,877,525,855,209,992,744,631,969,588,700,463,609,368,496,791,361,468,580,551,385,680,376,111,250,269,301,944,371,506,442,905,660,599,95,722,501,124,541,244,526,882,282,694,344,631,920,96,962,510,22,834,557,460,477,588,839,843,708,111,802,57,890,90,925,537,106,173,96,872,489,289,636,792,321,444,440,951,385,920,444,992,9,701,296,272,697,153,669,392,306,950,545,825,51,203,534,114,92,808,852,900,333,318,113,861,831,147,391,967,265,265,725,489,3,560,499,476,606,966,554,822,608,773,961,121,843,836,760,876,86,139,663,664,522,3,415,843,934,538,758,887,305,210];
X=[1000000000,946958,348541848,148847644,1000000000,237161296,120579444,225142252,146748023,288642095,1000000000,266420769,26856390,182003358,92970332,62829426,116076688,447904691,444195379,676814104,1000000000,228896161,139425121,177793760,709431310,115471499,164610136,32752916,680439460,87266507,211457631,251113222,194772075,112581056,252295008,169357466,44781165,251997770,107468200,1000000000,232421342,156673220,669099769,323681617,828066441,24897814,68662203,372647383,1000000000,1000000000,1000000000,146390942,31615425,81960288,13452965,155682726,9367978,500879987,216632216,123607395,1000000000,10815020,1000000000,435282504,451734241,23349138,61924795,233801627,159533490,130174348,86774498,50678118,14470517,85357570,118113084,109546979,272383050,801621654,70115646,186148522,204150794,378569968,11339698,49581785,61964302,36273148,3505702,1000000000,589031470,45178856,253599523,480542782,5666829,85289571,104572383,496309551,69466004,523677459,337454516,1000000000,71353351,290292826,382100966,187581112,2627474,54106014,233050861,197173141,200100438,462858173,656622078,325839058,713383677,450943613,73369130,444907962,621059312,27822076,146799179,1000000000,309136447,78731403,307279477,181548082,391468948,140196409,243273591,1000000000,140077376,316155575,488984704,64216167,177137886,68689208,741968511,977003,61594916,267775876,249646620,174341289,66688077,319921699,1000000000,5392019,594899444,88676191,56960040,250676110,35222518,187547935,160809680,216690236,142163659,102769669,185948046,545633060,410579346,149718262,1000000000,51684085,1000000000,747831744,72212894,149427658,476159787,388359796,1000000000,652162641,293415328,418072973,12697054,101243433,334195142,119463068,52093832,548408591,45577098,229607566,17665587,2090243,239479179,178724571,25035223,152022333,339454136,306399063,5350596,215652347,151315252,45716566,377461865,200138224,164343130,195458022,7938307,32227878,37629580,406919637,501752782,373731556,71386304,118322883,843401942,308813347,345161499,7265304,129777301,389378529,56321764,347449006,325054611,200072554,85314043,241069423,243616928,6351547,23424932,26060179,160814332,98170693,465725977,164891569,628030360,1000000000,12058497,187942444,510664667,7604097,363895250,320079644,41293902,418228658,52469005,48285453,2832087,4053492,77337155,245112987,1000000000,107622633,106602353,66725324,222243108,8442778,13886676,14388709,6888150,146159968,33720434,1000000000,185069787,49024640,204249876,14577687,18229400,8104253,166474764,153050026,14725466,129170328,54898277,149389451,1000000000,3314122,503815596,1000000000,260648727,5060780,52793196,670242180,716035156,194110457,25942093,46571157,9399439,92856392,131130315,37258123,123028036,76649599,1000000000,1000000000,159368812,383734886,5307971,168015130,448680663,125035467,50972712,135927494,67982941,413277,200613956,19501574,68517041,125503411,91144018,81173646,452210706,16217324,1000000000,658539375,274744138,608912100,56897632,435709621,1000000000,328032743,136516293,222605308,31777970,29038343,4359352,250227464,5755170,114825652,4106645,134403707,458691344,175002163,154583109,479634901,1429339,289295594,135490421,427805690,2068266,765559711,115835613,610023314,239543392,31059853,925503101,143151772,51618019,87123763,251033923,224035950,1000000000,11439241,46659384,220949625,40629810,175851767,167278755,792136229,109029164,27544438,59900082,202452508,322934819,24996781,255559789,64968062,7156389,171889516,6089987,290268900,8506809,14837047,23631794,78874930,2126885,289781924,561275382,172992160,499683704,115476699,901060571,21518718,258092034,526152349,279893990,402267137,1000000000,536228463,290314264,568601561,155169370,1000000000,300922910,266031390,26746464,2888543,58341571,474355749,865009,181422430,153318184,66753655,1000000000,22257652,22850879,757401279,139474696,1711219,132659173,811217088,54412938,1000000000,19229764,298383259,147650437,373131981,6171661,331866266,162433077,13560464,13392802,178126064,209563983,156130615,386050633,401047302,54559111,1000000000,671501643,3539947,188498518,116212398,161878498,356746208,246503224,368731,123813823,17411506,9104541,49531882,56019418,43398776,496735728,328184998,159466316,221660342,69146931,561389225,87963983,139509686,219193425,741119701,20503714,252284504,1000000000,135732888,542537537,209687988,3071166,57769119,126192491,95385936,250746728,20697856,71675523,226538819,274215600,195529793,1000000000,64768692,519569550,1976930,37218924,100986308,120111586,1205264,69456520,119262059,1000000000,965465680,421639075,136574262,10705322,50159022,874732,66760689,277598842,41134487,189235604,40088039,548859371,260390214,319482576,161591145,188414005,84417391,29432266,208292829,246045852,43791924,383413762,292009430,377801698,267206905,1000000000,81410483,146997018,110419071,99758806,70132517,276325088,19508636,945769347,37660482,819306317,15150617,30557490,107686800,1000000000,554484707,1000000000,205249919,1000000000,81908322,10509415,20026649,164453082,58657722,1000000000,362089141,1000000000,567317582,362191937,377035177,84735968,178263900,7321874,63588706,153895233,126451342,17762017,53594759,86363714,3917269,99049099,309543137,156138804,37919623,27572231,61603711,219381419,326861318,568502675,918945650,462104350,339743405,21011969,11468345,1000000000,844750272,43171968,1000000000,6676721,479913140,303004567,72909858,1000000000,300943966,1000000000,793720328,187894588,332955827,285283155,1334080,90770416,57295888,210313743,159805852,114733083,24790288,21638611,123673906,268304563,322628572,18214526,134796775,188987379,45032975,202982002,38276738,1000000000,66487588,82339745,491963403,428121304,815577,320248399,74036068,209509634,1000000000,1000000000,16073551,318461340,49060329,1000000000,463413874,1801866,1000000000,113760053,77515082,197799759,155995439,97336405,57138373,37695824,1000000000,5771368,706073335,926287020,187932862,24698553,73704926,454305280,103033870,1000000000,31005943,8344601,49599883,207579543,946755522,1000000000,54591647,2615722,262670785,1000000000,26308242,253740113,79334,210167052,129134728,25434342,82993429,83747001,109055490,341629906,1000000000,4739346,255833269,133110907,153130264,108747970,123360793,42217335,204952126,613891449,219731308,356110329,123390459,10163803,73048896,256351604,45987161,159675193,104664127,196779556,165028175,875738935,443775231,2989725,129899299,913835792,242762592,1000000000,1000000000,1014049,2286148,128428474,768927820,166574651,162105092,110406719,153914920,336023579,127868121,159190351,237303325,687940560,79221645,506594270,47420036,12746620,128215162,161586538,77522698,9974528,1000000000,31523573,83445665,287337242,24663410,295351316,179358479,130057769,810083,110928637,506459509,263506432,336799192,59811936,48310181,192963386,1000000000,737676758,136392847,174890221,99778902,377764678,285127528,239516190,749316048,9847356,251267236,404629744,277501402,241704543,344577275,1000000000,88270083,691000797,40487461,90021359,959025821,326790574,492979798,2958885,63140670,426978688,102377427,30352058,16352128,77800869,133256552,1000000000,204951125,1000000000,23241994,985854913,233199013,297128944,39743032,47917119,1000000000,131321565,2303253,159874362,40948432,166351359,154321447,3967201,458075903,133368017,1000000000,14922236,109250783,2622532,178641999,228463097,61697759,114798096,190005668,1000000000,22205702,670191824,1000000000,38448052,13072764,109774165,19912907,1000000000,106644603,484036498,1000000000,16908618,843959078,1000000000,18692813,333324156,53472531,31609110,65810794,253288272,98143598,50657614,214684283,14748804,579785225,660411161,743035,72340179,1000000000,1000000000,11737256,54355826,137658839,1000000000,152227491,1000000000,129974176,158707258,249107757,28714286,1000000000,238132779,170489776,7294305,162853097,177374940,184173137,1000000000,189742898,73082664,468681844,164449176,16222300,1000000000,2920333,71811665,28277669,14593342,972406521,362118119,11736685,71693264,304375131,255315513,304080254,464162594,549907666,455705,280489955,175306305,14699740,103906693,290618455,82155746,29114762,30212437,31478568,343223661,73341173,187957423,7105645,50912079,16166920,91578000,22875999,780834695,165311317,138198261,74452721,159595134,22358630,7014679,184663330,543416404,174211719,64923603,54155509,214902532,9082338,30420693,122714486,277930632,136450755,6437611,39918643,294898055,260423925,105923625,345997032,3291022,15712895,10791667,122733976,80850873,69386504,234652032,319880744,119397744,531783416,359000829,54099633,1000000000,15450472,66042357,63393165,4319305,36924327,253145826,385224588,177098829,236528256,644797869,315657735,115665271,233344480,154323281,82127348,168532489,85962214,640095186,97668443,265286184,85859601,4945173,347976587,18812673,1000000000,103447460,231605512,460396421,19812128,33365205,224693557,179465228,13320693,4884827,192721826,151160644,407201325,554379163,222634018,217740089,1000000000,46708040,228016736,48753846,107302200,37973030,559930414,421999564,757648009,144683546,33706607,98208237,296022314,119650493,1000000000,235816291,258069405,298000243,127231594,810504,657113361,597326496,54992854,4595803,1000000000,158490726,94379388,1000000000,34473101,287873717,29496437,151454153,491126698,10914540,335501694,1000000000,118044249,1000000000,24035307,211928605,116732203,136042292,76902993,47255758,1000000000,1000000000,67570359,365816782,189458266,1000000000,173298018,460827420,140735501,1000000000,59747114,1000000000,99748733,203655570,161265516,205615985,131936312,579514434,15575027,516637045,38545995,62845689,73194615,50504424,23000710,1000000000,1000000000,25335352,109753911,107565300,139760138,105762973,143114588,222585794,174631425,468567657,7985917,376192394,271271709,221712762,112343,108450099,413496662,58459442,17383111,75754742,221891986,44920479,119887547,649776247,29236222,362668897,1000000000,196483291,94306220,214069417,838846899,348338290,147693475,184094802,1000000000,151326833,15364552,129254759,1000000000,118688578,567955101,86262912,1000000000,432819136,107480752,320072212,360636794,77665841,208630896,185289883,247370063,11592869,894351962,183455536,1000000000,278422340,25794911,58550125,34362274,1000000000,193615417,39107390,247294611,1453406,763461830,28924345,207555650,43944413,53847592,228455855,45508196,250333875,3211709,27538111,162982280,72173645,56780758,42576669,409129232,11799484,225807390,36049206,37663357,84736656,193258763,8818182,307631566,146529629,347235115,77686582,118697815,99849627,117388858,128663976,1000000000,281144507,172655356,156780338,34829778,409214025,333927129,279436719,181168795,73524591,1000000000,195249720,77597567,22417378,161758614,147560924,10308057,225007136,262476048,164313537,787950883,140721266,83815108,287900379,142444501,1000000000,769253004,1000000000,1000000000,44494440,123626837,692421045,59896357,69217843,213999565,365127684,51090971,697172221,1000000000,14963737,402052348,10907492,455324623,396630693,461412927,56913831,330463284,90517856,298161469,399191209,126396227,175677456,880520735,1000000000,231708414,105786325,176528838,149049472,141636602,420011660,75685502,649213484,12789243,73384714,175878959,339978717,88136122,57867915,13338127,1000000000,4604647,288754831,415014992,89381737,21647057,624692610,150763758,103984582,167065486,8050453,42582627,10533568,55172873,692717681,7291378,25815288,117238142,1000000000,757397706,14191661,488937150,1000000000,181116246,117212113,93595041,823808385,159050519,36498403,5869547,719893520,281264833,137600043,432929696,148165708,271454140,16972395,51883935,1000000000,134628714,129135013,28623970,260732074,16424469,255312102,71765330,1155990,243910134,26102656,108971401,224810931,319666395,89213141,10785911,64887514,241812375,560129280,333940427,893372435,39868568,771580696,736735764,457410585,235584767,1000000000,53276733,568788046,52258176,24007384,218532966,73073281,20454516,771106215,213423876,74897723,15501777,411928585,53170869,220259216,65659546,19820907,16710095,726776227,86720362,121222112,227170447,24281022,1000000000,1000000000,404573804,38468045,303002760,820917782,19029393,134844186,345833483,56210294,283408072,445608463,81582962,729882900,36464783,465629300,196916,20852394,926387105,11973214,53609698,133816545,555449495,188495457,16945398,277355145,128683980,538961698,117555465,185677792,54613204,258782728,50824406,537201548,35330174,21395555,432025579,286564485,213704823,48738032,184299057,922204327,123829164,76753062,299169901,19678383,24752865,349239912,151930378,20510734,553091106,1000000000,127924407,194787388,115743491,1000000000,4322520,1000000000,125108463,262971482,314348542,157434383,327340075,240389734,15859049,120975450,403091643,66674252,351104390,115668942,464479189,49594687,2035173,122563070,46558212,635732,168219180,16283162,2052911,1000000000,94158126,5125804,24167063,112337761,1000000000,23572155,91322723,59007326,48865789,157653111,131095768,1000000000,72976274,85985573,22638817,95176206,153375987,74881901,243274317,15093421,29756957,464167410,35662307,61083520,130167238,847861433,127336423,511242392,23080487,161430929,1000000000,589865099,530232747,171216435,16112354,115496263,109831314,17179940,73755325,17753339,89770124,51710519,125513244,151901365,16740452,12525933,219691404,263443097,167827833,6867322,437731810,238300879,33733237,172595831,177556506,30522824,104770954,339088060,509540540,530146711,278840674,355486457,101954352,16386617,56551135,35536739,124669026,90833093,375020677,137990642,5190519,36251733,1476724,244485917,117064154,1000000000,131570161,21244869,3297257,94130751,1000000000,282861952,413164425,879509851,1000000000,9909917,7567269,195968973,32682130,489394925,40938673,48981577,21510456,149834489,37139338,1000000000,42555222,1000000000,244909630,321346985,264615894,234227220,827386298,7412038,229468952,338634702,19641249,972666505,31647082,237615212,3838503,889426527,39096,95930858,118680740,68676999,344152502,65234070,252909,18122914,73979273,43775338,123399375,94816377,151021750,733860133,166266634,811294310,199974769,70975565,377082915,221267427,5314866,1000000000,222284640,59980954,152376643,275398256,167211390,554839174,1067093,516628676,390523580,440871526,1000000000,1000000000,428292,26485028,20932269,108804453,619758,76555958,12602245,146292968,2354343,264105787,65044691,67565954,295165987,112898973,199754112,243647961,119079767,169947771,177665474,501357516,1000000000,184648477,21713298,37926651,306886832,387761614,1000000000,252315947,895061470,10358619,389058484,1000000000,586081834,202463896,1000000000,4451999,434174327,505419964,761378074,305378161,582699172,12101089,210478639,49118556,29173465,781819144,1000000000,47650797,31264686,148329673,156656302,129680943,39166291,15195950,19776337,356547536,82573165,1000000000,155944834,180311836,513399831,481327153,124874108,287512496,1000000000,138961964,1000000000,1000000000,37281352,111731986,87521079,538076172,49931514,33213246,25447516,243299811,31807769,425565338,419673,238017410,140908038,140460802,1000000000,605733756,531666894,84578885,264937901,214648435,56594203,7806747,476341643,61001039,538768965,130657471,1000000000,1000000000,239715319,1000000000,261368207,164652746,87728195,1000000000,35520639,76959902,58275767,267351296,40832984,75065591,331774437,418081094,161342616,614452001,64887196,288331333,114287639,179261669,247073381,408430401,507573624,52891280,80326934,336086776,54707165,11278778,531754021,8470863,600095440,229634989,84149191,139992948,21419443,93696815,233832160,127280774,4393022,32234224,449319309,1000000000,315093908,1000000000,260089375,105293095,1000000000,1000000000,60413348,718740243,478198440,118029425,91315101,4102344,7296483,76846616,943787368,57994096,311176043,588545038,561718245,45704556,142272237,402603375,58652852,36224711,2458253,176707508,227210844,6105933,44814452,5496452,20504235,42076996,10338259,213973905,691852172,122436827,608255231,1000000000,41513375,16595116,49526675,213782135,32217525,607707408,55184815,56009420,93895457,85890347,595004510,10140310,336730532,123882247,769293202,63935041,115746804,200080275,307753733,9429701,602689201,59500913,395277737,112644917,206734974,489327744,296637,593089504,42199853,970034013,752952785,21668769,57223153,179487183,539231828,142448538,1000000000,344496336,56123818,235913357,401380521,347886786,68586534,33306862,24927354,34063735,180530993,2161909,491370442,325227353,100175199,41945895,109816153,9711459,225802964,471343749,26425677,36479054,75727778,166136349,51391148,29061660,1000000000,41469852,392120688,42499019,1000000000,9567229,101379386,146427750,1000000000,393085749,14441212,1000000000,436812530,127282347,130952420,1000000000,112449652,48023342,105010416,112995032,888904402,123674535,1000000000,586967098,109184480,1000000000,57610882,150153569,516827072,268453,566297965,336234458,65522936,388396472,76618549,71511819,734444584,890060680,24250529,3308960,21439614,329464878,26555839,139333298,503347253,43474684,348686583,13825877,40656,15380019,96634223,88681274,539468354,47862187,1270707,499871099,4444286,192983409,103402492,103704888,392227303,440847848,13088683,588467183,83727901,55922605,9830124,885097292,77987904,55640114,27412615,1000000000,33319482,152479998,246063419,86368814,147505144,122851980,6471402,23102604,290483115,766573566,46119803,549238960,242656889,189437712,214511214,58253879,450441879,74792759,64227568,246238521,1000000000,98569188,15566312,108032824,103116930,137392270,28165277,988920366,66985610,12101662,151603100,144297227,328474618,166244515,331071203,109584842,613635860,43688036,41345311,3102022,344004704,1000000000,412448787,638996342,1000000000,196823788,512749188,13180846,522541564,264142659,122837436,0,272453709,3836509,20440874,144490281,98416945,117865168,330875186,227659701,180143989,142112920,16711102,220362305,82486986,455251667,1000000000,20293231,1000000000,486898067,242171342,1000000000,444211258,34331849,176687035,404431119,941303304,94091471,157710013,206972737,3346672,456818030,152918508,410292214,7943814,48204989,1006773,22451923,624364,510709318,112635439,180571500,46954728,8880799,29731925,60195436,596681281,220110622,19279068,697557123,1657344,235290267,280111002,41582840,33200302,66728804,548362893,490586914,25488770,128709333,6888584,21621625,1000000000,1000000000,41648718,196232189,28832244,104889804,1000000000,1000000000,482362222,177226332,1000000000,46936434,1000000000,10685923,1000000000,74621170,431078277,505111622,27730828,40127811,169584012,29308619,26855126,498713008,255469547,1000000000,978820116,814855330,525500321,39219460,443725219,422646785,1000000000,7724611,171239082,787218372,171626115,124331060,80823996,1000000000,28115256,20084991,92853838,1000000000,127243330,1066185,1000000000,147477116,533719684,356907583,162632429,144637890,43737044,182553980,413950963,83125824,41561858,317900580,18939233,249485894,406306472,421491834,13726411,1000000000,75574041,94198524,515614653,1000000000,72690204,215683534,434886136,455826586,624323536,82502655,224667001,219233095,258483026,1000000000,53034147,36902733,441217696,165694341,114411015,58486672,339501524,2000555,759902734,5367762,812001796,309438625,1000000000,25105164,167493412,66775718,18589813,432896257,130990776,159407813,16274333,130488506,156572006,382051581,323097914,84199130,69010352,53707004,235414680,310519889,16560300,653084412,863260136,265405985,1886321,96078489,350574970,42062914,755243791,756825335,4200882,65726803,150503311,95230690,33895550,28736467,312109221,34047071,501153,39966364,48154433,583299705,591835571,386172028,11589945,152067351,612489904,211808758,457722773,1000000000,366062589,25221427,15123037,203014018,139754747,51815849,218346022,343031908,1000000000,36629376,23564732,105321194,349591784,404720127,595673281,45079922,468395442,188602132,81477682,108748893,79963723,22256271,59740646,127107995,264185401,346510897,17888655,23323195,56981554,488385871,152646371,48818592,1000000000,1000000000,148649278,173524317,60853491,1000000000,106442185,51287532,413565163,272105686,8635370,159937983,209356033,20508549,487440676,59279724,691569545,245143403,402031891,46801044,8380058,242427053,15154254,14280505,279838221,216190268,1000000000,608708774,493046697,1485387,59252948,30588431,559106953,40968954,730834615,72856138,216115729,18507266,708827019,97363890,383993871,343721960,5289233,25346403,261239018,132368227,165153751,254668438,164921504,172969326,46665616,102527405,173711811,40469004,352803261,1000000000,5546982,1000000000,151296900,34496737,35018853,298082317,107607781,169767488,173611575,173464949,214870764,19665738,121429863,1000000000,50020331,353420603,9480920,6419488,60898755,73037835,164719312,101200967,29558473,118627849,704297048,159845454,407419567,136869160,51518286,480181713,113356693,520047122,135529107,153307955,141375386,1000000000,109235878,184432027,125496573,275218,60043004,276710827,195968422,172852498,44018220,53451218,315358745,292756104,831335760,1000000000,305830884,868281,70281324,36374615,292910229,246639770,51971737,235392127,1000000000,7754676,19802396,136473805,189350647,160207527,68808885,802280235,1000000000,1000000000,122599485,337329412,120155697,280191879,1138604,59343389,127429348,23811725,924387477,749197895,164089422,12013192,51776540,75836862,55225932,188156013,55935105,56109736,962021748,17438356,117909953,1000000000,28433275,596183194,33261405,12843741,486030544,678355695,392831588,468866604,662287432,657197417,391498674,643660860,460473620,14578517,226954144,1000000000,13910508,437145270,1000000000,91201146,858707623,104889768,2943934,403596316,22192512,54569582,84036115,139084152,741474465,332783018,588370514,1000000000,291171303,36253193,17078934,26948316,6110926,478889004,133263070,4042706,211901516,297960334,39794234,329446770,256770041,40936660,1000000000,727942650,375483997,473838665,369169962,376225871,405315042,87463407,410420563,199446095,103931585,213602317,6283688,71996238,128723961,4008837,628273124,698165826,195714939,1536292,369277452,93704570,184536361,26256970,9811364,615339809,79115239,857605730,11325600,65180107,191021931,3868548,264061141,1000000000,85082707,370807110,448843106,175342815,29500462,17341152,1000000000,173572848,2620934,71443999,330745496,415788277,41689056,225017334,53070195,91703238,75226621,521562583,57188447,33559265,18742021,425208657,103487210,74657696,339593288,99925753,5854530,144634763,1000000000,67445354,125416897,47924877,333564601,4133419,29411630,109863228,298653409,1000000000,6016701,171136218,102058108,245782991,521953739,243790787,152197904,262464555,518792797,66846949,135282924,143882284,531622867,3149152,83386271,259109807,884462741,728991440,168455951,858944296,54843249,300670200,1000000000,412549408,593231442,533799015,1000000000,245531266,375077246,20552810,19255212,159610767,79281250,726684670,66693191,11496592,447196821,190021877,204011344,57434224,464414722,27655192,1000000000,58008093,61983289,230637452,77295011,634635668,11965487,139308584,117583026,260496473,22870303,1000000000,123314450,203889496,13011574,236699001,183079661,1000000000,90407416,1000000000,1000000000,8059621,1032088,724132398,1000000000,26563298,51394838,89067681,58745626,55672643,1142871,93069426,73932292,157763849,39451188,14535604,201933989,135503174,23275028,163822878,27060857,318459635,387231185,12479884,200609943,105040917,155301492,92059868,89110564,80036003,303238584,47952902,391646460,437117078,99918057,165105685,1000000000,1000000000,35652501,15510594,136361433,144278999,61284944,57243150,15373976,16227155,236873950,597187955,5343455,46129700,26061872,207497028,242306860,160693365,849512706,136286376,279366363,129035107,273845864,580479,193650539,1000000000,219600894,161076601,74459096,51501757,472093551,280135719,102703872,265294428,13563875,53553358,68437846,53528329,139483096,55011899,839347187,178625564,131993666,889335777,434488064,292508440,93063357,116761726,27061285,80021031,90918705,555740878,74768887,208191082,121630463,471177536,60724628,35463442,122333125,303895947,218904327,1000000000,19759058,37914093,1000000000,45711046,46654738,285829803,56916570,248842523,465527871,29119043,13494687,1000000000,20724169,463150103,1000000000,53199561,254469947,23237196,1000000000,233637006,14330244,99125652,684445513,666844745,478689762,21855686,180735487,319685355,26520499,113887879,37034698,22841670,46035298,365237107,106412237,267256176,479718777,284937475,2664108,214044242,266989152,1000000000,158493448,8369410,195443583,89625679,55586904,14816405,314970739,91845804,270860186,10118974,42767582,99528604,182114978,887038314,89680343,108509813,264085745,11257723,124919690,109400719,90759530,10196245,212512355,81803724,479146903,47456469,13429951,803301595,77339419,164842205,256694983,884341111,1000000000,248901780,34342901,256516988,69737099,454611623,57761052,2165708,43842225,154653846,448109623,1000000000,66901617,5356812,649999534,53018797,437389081,73372221,1506583,1000000000,60573769,181734748,1000000000,537042169,24346454,548741204,298937211,830953394,23172031,106826957,1180844,10978424,448735589,192209389,446256200,298390261,104650230,62630614,176514545,709955901,21442525,121234030,493356815,144452290,411113043,79066062,2127819,282508701,99901014,1000000000,419643120,8864866,103921438,156124896,27284844,2915609,1000000000,236312380,1000000000,902337833,466731855,58479007,2908959,124986164,110931514,148377704,1000000000,674662,394838139,2921521,10942221,617029159,129671061,63837689,369212426,8288598,115130497,420607549,1000000000,1000000000,23396142,1497040,66234729,390523835,52011628,270428950,65876731,56020257,107178935,9398605,62461338,223880590,555468415,311812316,481252231,302531125,111127943,1000000000,139388063,751448296,288562713,260327850,575666163,487849414,313801930,1000000000,217809781,34682257,12866798,444670867,195830384,25336077,482775613,71826029,1961297,455537908,575228873,109180380,27100844,142465330,129549022,619156621,673256065,50772628,450399055,638986476,1000000000,1000000000,291649813,15624633,79714801,579614316,4986761,1000000000,444924494,1000000000,176072994,666114122,111510248,34535338,102386942,214438549,77986777,19540842,285112,1000000000,30782938,125789333,155956867,80009376,842148580,233785324,20040116,354680949,69505802,154078337,299284308,43997668,113015084,71050290,1252349,104297980,190274399,883351355,180003666,1274635,280681320,115734043,25698792,276110220,164641413,163829796,194397477,177710924,181817595,1000000000,72750580,18648651,165286124,11986534,47695116,149263098,78657082,45001035,15145211,200337231,1000000000,28706998,1189420,144430106,293134562,91258274,413281808,477442455,828117,712075,1000000000,52694841,53477019,90938998,274050122,382520181,1000000000,12136623,155850070,136806572,143029655,83320801,62185564,188258339,85729819,1496832,473256062,81489112,39257407,154458858,19456771,1000000000,217037650,1000000000,24166117,118910311,63198662,19693249,19918106,258490953,894717578,20255472,30623870,117540877,629468950,271835565,204049973,212675763,107735544,256119382,406582751,508535589,36821156,1334448,19692582,517568150,506984875,61684198,234699608,333895721,328313645,81039757,204727000,284430352,1000000000,368862779,103543590,235217850,92123244,705657142,997931325,73355855,244530968,246228454,656996767,8021008,202076730,1000000000,653490256,932558,25135765,91708165,932765332,22617502,13039514,1000000000,1000000000,1000000000,39732943,481888591,101556715,4746922,1000000000,5284894,668616582,20340984,1000000000,55146172,182822823,709322651,171858364,133697050,47912395,695814395,27974407,1000000000,22008559,40041202,961196613,74838028,485188244,146338591,323321274,7748491,472656274,41459126,38177319,186134051,393603326,228435274,241060145,210784741,12005584,1000000000,3820757,234185624,1000000000,30604101,254713704,209952584,116492310,179151994,362951719,15599449,92821814,685481856,13156376,130917957,39055184,1000000000,6102754,389476330,1000000000,168926754,169404160,356784444,1000000000,66997732,575001711,664081602,1000000000,225952279,130031309,318139,138056840,32186685,129476748,708205290,173257233,1000000000,172020148,236526672,78965828,51631367,1000000000,34062105,1000000000,20661211,22144831,56443181,138191733,144858014,76435744,40915762,415747859,129764629,1000000000,1000000000,51726880,25963859,21439775,581326432,386700342,343653367,95366950,333515412,343967372,416990739,525417292,49728183,139883521,498457718,18296424,859530786,5750934,548988084,62372920,155432494,20474055,1912129,10396364,592830300,179486268,209477630,142860906,132705994,84549575,112351505,1000000000,143435142,119308007,26696266,118486696,1000000000,26774095,23541892,1000000000,64378733,160784686,34213744,953495629,758996888,703523551,69946073,29089153,151252959,235462692,15292622,42497376,203534705,824279533,229316814,32754,1833760,141878649,6939781,33421034,321646789,37835336,97332663,9609279,405869794,411676319,530900596,8411306,201145695,6566842,430262686,1000000000,223315834,367434883,761303215,54968415,12784002,889794084,165985882,169832736,17404428,355383566,321291748,120292227,79654664,85542744,298380353,3289713,247900270,94795510,44459322,1000000000,162192744,43461177,126790877,291384208,69393612,391810335,13128813,51812440,55964110,230188130,1000000000,383493382,167452511,783872131,85749213,192184826,439775496,1000000000,2312174,768130012,175673970,397464599,380694197,94172015,1000000000,327613805,99644884,8795920,182573846,14105584,194969277,32096470,91135263,310935685,124123008,4023389,536648846,192786415,91805283,208342421,78926724,8318526,319131768,12317233,275142131,1000000000,163218742,56819500,61882531,152432481,114314085,457010199,61683163,89505197,32521694,1000000000,134420482,240167403,351721534,263503896,193893902,100834644,291339401,359014447,46556500,648556123,1000000000,1000000000,89010924,16980877,446835149,495379364,127225068,346303937,33205673,118410034,99767734,145043888,132876995,158245603,5179060,284724037,16403302,110563075,493918848,12427210,42091586,238075141,25615679,181686404,36986383,2356250,48405215,57568326,1000000000,130754057,5701041,1000000000,65604262,168242687,607762235,53014951,328556841,195420420,816960988,665436830,145540748,116248826,1000000000,256792220,62268942,113848924,1000000000,166850050,190783890,14904250,1000000000,236807621,2621001,89638003,601018766,48240249,40952571,79337488,963963838,75099937,192721828,281564556,120076353,7984152,14315488,225053793,218477707,58691963,915291323,396851848,1000000000,776314178,110435551,166164763,1000000000,297081813,1698734,204740154,1000000000,192540657,1000000000,15800587,45758152,112098951,1000000000,269638879,318020507,1000000000,232477634,66270883,167239917,320177061,576871644,132519331,144711010,926931996,24793883,151995114,1000000000,93797076,35904693,158094672,86413758,1000000000,39213569,1000000000,4653338,61800950,98178606,138121835,98333563,180944706,206895480,104816010,582146316,276598060,177981702,582519,216099339,209998049,108487323,173513787,1000000000,236134782,57153217,378904866,138946492,286105920,1001369,9839271,212801418,1000000000,403503,390503059,3411652,211759903,330647,864216783,15179412,37013603,553612072,114810101,7493625,1000000000,28282206,387542902,38352000,203534036,240693511,518387948,1000000000,175115893,407822337,325301556,5634542,144923023,19691785,77634081,91911596,277690933,9629653,64310367,518621259,298497703,992429479,696668052,225353674,114433052,262286606,49505886,240159181,153661114,73782700,1000000000,2342377,182049661,538640263,4172744,258011800,15610268,15534054,297732618,125130761,1000000000,78277767,95207450,195166224,59286742,101962644,129278520,202678545,39777836,197500973,217740241,132526033,48113450,246566790,78642687,217169685,10641367,75903327,77016792,129209047,529837191,324850479,425761888,176991742,202527513,1000000000,23170192,90951197,305441865,165092478,602443645,125373763,158954967,1000000000,212342322,211914162,213293357,268865389,347907045,186502357,4467186,329175598,194093649,164823808,173572216,301830187,267742151,104830630,315507936,1000000000,23656107,280839504,25543564,308249109,55924,28620713,143633202,292516454,25785443,264418692,10787188,394382409,1000000000,225848780,471466743,261365555,459585103,73739219,605237300,76399415,71610,224557124,236737188,3862861,384347528,1000000000,253823046,399203,93851189,7522762,47349730,148999807,568505540,717708592,250792509,378304964,120401009,155698215,275408905,303830885,240485,84828827,127894505,61411896,135420777,1000000000,512658659,278048054,151225275,30900592,235162951,126568114,4816237,140017035,670995649,541130030,71462715,34076956,239642320,76907836,1000000000,34945892,126559184,1000000000,74673761,95307460,556115667,1000000000,358717804,263314562,22838953,1000000000,6600682,714786862,1000000000,505277072,8468970,167638050,276187,1000000000,70060,95549675,1000000000,41936946,94605560,222274563,24077622,119960281,162476363,16242817,282175507,100571697,75184839,10696460,508099617,296434121,1000000000,566121159,760659505,1000000000,412072978,480747324,667269328,286996503,323014748,138885225,58731111,229157419,126151293,700491843,13653037,366380746,16736065,65469258,20876245,316985674,729337323,1000000000,412535146,303817053,55382215,346158052,8936991,30014794,1000000000,1000000000,281283067,355147248,296229642,500359777,46484780,46429602,78469301,894203895,6372853,220025083,271176747,1000000000,60162105,113176036,101610339,160306,162352026,334746514,727102506,112609638,455779549,488870359,27973764,33144482,80967554,47664228,102182176,514365760,1000000000,415975501,41722996,12650772,1000000000,190253610,352524039,57302490,795696666,1000000000,8744757,293564857,4985691,177439686,217098494,26757979,66391996,152211934,368164869,1000000000,55934731,416095252,406838944,146261474,4632343,1000000000,365656428,122248572,69498378,68899262,326969035,130515364,71747952,40610842,35924074,143010624,383362244,80034378,181261453,133633476,29614016,106384399,405449281,59841656,29407139,82366984,235212491,41246571,1000000000,124732954,200429290,124842450,122482414,47650952,71793918,171083383,36709529,181223208,702349259,295587666,190823079,237938815,184039253,25282012,65204336,32465497,258900270,260909694,52892317,112668265,1000000000,1000000000,24470486,176796374,484005650,56265597,321784763,623050,322915842,582951903,34174015,187641574,188207123,513682925,12253169,668349522,255838358,1000000000,119660770,213222717,256196874,180131626,835887102,20226919,1000000000,41924711,57723217,7349981,125175772,51578748,221695701,157688237,375796692,1000000000,288487375,22433305,102660745,628688209,291158133,83855984,40333518,380883529,306222844,4292080,1000000000,70410170,1000000000,1263508,273127589,80224823,14053310,10146151,912356742,122138591,441221508,394509840,55881679,294126568,209731887,691190242,46362669,1000000000,418933772,337753036,492148470,85785399,3532841,1000000000,55009193,368801005,151102627,234776771,1364134,1244818,24777130,125324050,220968842,259004557,107210626,589950697,126515297,141098063,9320685,1000000000,37614634,424065069,212427687,338652813,71808232,26945988,986801684,125997273,1000000000,154804697,26093039,51196927,287656436,1000000000,32259748,46960210,80691927,116189343,108950461,32609607,185538111,158576332,172866175,169556050,9798763,90756593,151989412,57129445,3673002,32869435,2612329,1000000000,3016250,1000000000,122629222,145756038,296332536,578682,208225093,1868999,20103096,1027776,519561326,1456958,523715614,14654660,84994596,13891492,31683202,105384922,1530989,165484447,235296621,339279060,1000000000,1000000000,46276759,60242952,665624,960609481,220635342,111960381,402886949,324783402,46695439,133758357,1000000000,59406678,25895538,3701106,540667970,319315251,88189562,30002753,333974991,4755067,28447351,53130183,10572761,1207832,401409155,26928643,9717804,99648333,446379271,121628345,987369308,729062138,378554733,576332496,18005881,904617,154954282,53088985,317680,43410302,1000000000,24508840,41033112,51360343,6139403,214697687,76348725,515114972,515075586,11226190,17414759,332999479,128537644,113662597,1000000000,20718409,1425229,71131769,65618877,482196909,356521634,82957201,133338292,5813446,95399879,20232160,140754613,16097857,450706700,134344176,1000000000,717555997,1000000000,145670719,219753633,170147524,940041768,12826441,1000000000,336992261,323798765,123866901,1000000000,1000000000,9995408,1000000000,1000000000,31168325,400505616,181508591,191836280,82842105,1000000000,48309677,209898736,777754531,85712430,18336495,3659043,104574658,13948786,4698176,27958099,68457879,270065311,736415268,151872033,673523439,77822449,114018894,35687626,343751724,46694064,1000000000,123461689,245021379,1000000000,154814483,332583603,50593663,104965748,227623718,191590732,118420005,55525568,9018948,145824844,89538012,328626048,217353935,1119153,760440556,180748543,493886490,68363924,42737138,78347418,546654678,318446596,110620895,48611765,11750056,183475311,218204663,27746598,506994005,957272015,13234809,208750696,607638474,1000000000,234824797,309640411,79001508,465045840,2746955,1000000000,681893776,541315944,668264425,287873854,200870799,127929758,384132227,1000000000,253459770,988929656,96893468,94448726,18862060,165449103,136904993,201511934,440557581,253143293,306851169,56723044,1000000000,12929617,345303844,163607467,64959440,70619530,73809083,16733669,255395826,513420309,31754060,117171142,1000000000,1000000000,190387091,1000000000,618282192,985724226,178442122,118635946,152330649,3423366,10980815,36610757,233701909,404803692,135089100,443046304,304767,191875374,20834565,155563206,193059496,231233875,54049843,442455207,18539991,15046762,337732448,265478101,216554744,97058386,1000000000,5990175,256556521,54880503,24092994,24531032,11758653,364582404,100100958,31812503,223768910,52957970,839375775,737645379,46075169,128387436,200800152,1000000000,98316133,65835896,1883710,1000000000,1000000000,1000000000,387940198,449125005,410880906,563997587,223711318,226512882,224954175,83860002,277594641,29901961,1000000000,51169495,85577942,318369417,131324251,137693197,11492499,357230121,321260061,201137001,290744400,665059024,1787814,1317306,67520331,297850146,100711145,114189529,65715755,38858838,160276910,571910985,201322035,78820716,99855904,334361353,193824582,428390485,112966502,35090796,320928468,153134198,532625591,8979410,787668757,899715527,247101537,456598160,467612819,148432863,607796258,76614619,37064288,53458983,13664455,287619871,85595606,37143119,1000000000,789828292,42235454,179383803,1000000000,926484037,170363230,989178939,197179376,1000000000,54733028,117770154,1000000000,1000000000,1681711,463221439,680295566,12148994,15565231,106011406,168134357,119309202,111930723,274183074,429958038,165544481,244846789,141810678,281973049,124034843,289296449,262078757,183873392,12745779,989631578,333563099,1000000000,1000000000,39246047,113537220,235594274,187171098,170491025,59478215,1000000000,75634722,92325148,3077079,689864608,16960134,306962143,1000000000,6287930,65884881,459045803,669490680,103141357,28634970,165159488,13425830,481138851,142928496,97096432,255331028,1000000000,389383812,297022,639375657,32551583,155585879,161747,409608750,301600083,193921657,199630745,216713897,24312091,1000000000,135491380,1000000000,460376713,83325733,387776348,32833879,55959466,31231606,9921196,81575485,818519592,117691293,67183695,566029661,151810111,656790124,430509713,63186511,792895838,133130712,113986525,16540115,25161465,1000000000,702934653,143917145,421514651,132803863,269524425,11116634,47828933,180734563,269201521,63944144,104472463,199058638,1000000000,10963366,89504700,241385232,161449174,11895829,252497296,676119434,1000000000,67041472,45117509,463723569,48091190,1288780,7964277,121223288,35053403,60927144,238863093,78365695,847236498,143764044,244120508,168383537,891307375,367042280,376237587,280940440,287723508,405694813,291803059,7813438,78023748,1388704,200147081,152770837,366037206,101136869,849537608,59211950,688944277,115254425,6556341,989317390,420052168,1000000000,18256645,336143618,634933047,1000000000,241568994,196095015,51241941,52661747,22801899,34293871,164678352,356979207,39398179,144525886,14677781,308303992,118857010,112322551,692333952,51248418,246423143,176148647,1000000000,107718972,28863920,38735507,55985353,1000000000,293381113,139674277,103191207,150643337,458701855,14300262,42677988,40380984,981310,130958954,8366781,1000000000,579516250,14000480,86709939,275805331,152262983,19089324,1000000000,419045110,1669732,1000000000,118303724,580687888,248620522,87151798,1000000000,89043350,29806688,25487543,4226248,293985456,67239460,241889525,577123743,1000000000,19179733,582517479,77645294,217214919,20665115,10361155,325617442,695133493,140937911,18772429,332329927,46405010,64297933,21737652,13617309,70263042,614933727,1000000000,114821545,127619352,182100955,44992376,406686036,581340187,128272305,1000000000,31988540,37898015,36455600,253637311,351757037,144535017,131680426,624343653,24203026,28099877,12476990,134145402,292697748,232234085,197356322,24661813,1000000000,122446689,62070112,70143673,318314293,60749772,92136942,560888378,114441689,85706138,298840228,95225724,82726137,131504673,771197332,553010249,59520062,427999359,62328425,178880217,1000000000,246403001,586748307,201001658,180061134,314189932,288978732,74397206,493710036,946061471,476529376,349875661,76829504,336598655,198086795,573504076,439433175,140983596,184679249,103143202,76981717,3464207,34482744,470017852,161805982,32329633,682821190,403609909,23606286,254982527,544177035,501142204,361384660,217454407,110392535,7602286,1000000000,1000000000,227328252,21266954,965111593,578681350,642912692,206939472,123996121,20393345,51846708,85758883,1000000000,228191108,50293301,43784194,178305169,143015087,1000000000,800343847,109566353,34881577,420406565,782806857,51914351,406058138,67788482,106461246,311262972,440591556,1000000000,339752772,241174645,165439260,148714969,85260678,57002417,432530720,9047002,315866230,1542723,796929633,257492429,7229065,236647661,18556733,245428085,396621039,615966610,131310476,70980043,532156547,648424336,153456048,239975676,55617768,1000000000,119966411,472208398,1000000000,52065523,621058555,127629590,16907288,10397810,85214194,2777137,328226058,31524471,281842849,65290911,1000000000,442032684,1571076,151890889,1000000000,387940263,157279624,955137897,393967412,93354222,53146648,107769844,89657909,106281708,1000000000,33437427,2998467,11709004,773142975,132767472,9865944,1000000000,224678196,14154467,175952612,1000000000,2441001,126048742,1000000000,157965959,390614668,58876620,196413223,1000000000,405552018,199107031,23445340,1000000000,285932350,568928587,306568888,4204344,476828231,340942068,274872669,611637813,1000000000,106402616,1000000000,238565598,447342070,580342107,1000000000,1000000000,142530268,111870512,277672473,46720233,840161309,132196091,1000000000,55774930,377548455,1000000000,28817740,469678410,22527290,164174787,66211235,96669106,757912883,94381352,5029123,375420055,150975447,36601482,47372768,167945855,167172651,305633253,185118501,302778858,1000000000,32647784,672594487,336139732,27346144,29315945,1250892,1000000000,529662039,349496769,1000000000,45910145,4516030,644786803,13585470,45167876,1344020,19328749,108563255,62303611,822676027,19877317,970040635,365442803,75606801,209371635,167013995,203520630,7272998,70148250,1000000000,173006000,64716512,95497969,63723828,237604665,215590134,69591822,1000000000,1000000000,349246012,268392,70263792,52613093,506882188,139487087,151386811,91900250,211803481,24205195,787486654,1000000000,7629596,64668731,55890784,247220388,152593563,97877709,249914894,44513769,132540820,76402736,230618817,659998699,201488615,104530359,153620392,333709743,532339208,77132060,450197033,126274144,904715590,61655385,250685690,48893667,650698548,1000000000,2113391,73741170,36081068,40161320,27051960,44921175,175045624,21217149,510595816,1000000000,643731154,681764369,613398920,84946486,53044032,267643458,11228236,302286812,568473186,1000000000,522452356,161654207,68622385,442698341,1000000000,12395904,154193408,112687918,1000000000,1000000000,960160333,113637912,147160494,767612245,38161096,347900314,1000000000,36918993,95193399,109821869,290039442,142083588,174031831,16967498,195757161,50260251,169062288,12387420,747103072,229169876,1000000000,317066684,24647544,209709621,288450900,1000000000,23135583,813634526,1000000000,440633510,409413493,474473868,1000000000,159160307,28436003,1000000000,17794865,117392216,396631672,265870564,34815168,129676599,152568949,430271852,466840191,1000000000,205839213,132544137,46324449,135017121,301265439,186573746,143790109,147448707,38737560,9133237,15090211,84490659,143424570,41898284,148215384,277341722,75178985,1000000000,766220035,33278710,73928374,26135232,113209955,12794569,140631046,43958213,176161823,14966175,108689692,78073265,28073752,363314051,55165893,146410000,76044103,101582535,92823384,93838287,536796361,45765847,60526879,39060443,120362461,27094874,259040147,1000000000,1000000000,7608215,21730490,716942829,67832271,34079469,1000000000,1000000000,242345391,263210093,3782650,42764374,69632810,536414453,325430365,88136130,130795027,786241743,27819188,32223365,898620279,59615978,83070229,20094375,485373439,99214859,78220611,1000000000,405005159,466171946,1000000000,60142889,28141415,2037020,41230143,504407308,1000000000,59364398,9328393,396202548,306917640,614255151,1000000000,1000000000,54378809,48295914,84668048,189731166,152924739,1000000000,509287,357631746,328493400,95061545,135943810,281601394,5542981,704466767,44070694,66650751,80828959,273581288,913255771,83372602,289214428,181810002,1000000000,2694075,21908495,166129117,17413019,382875482,97042658,43177182,1000000000,114614077,55083014,351487678,172617045,520305429,416559270,128259238,265523079,35198355,3575372,129370268,42771003,9162910,46678596,276885252,1000000000,43608494,295361891,1000000000,740939446,60631826,136245498,782963870,22718229,138008216,1000000000,78337379,40614346,1000000000,839022604,483362553,68423399,278087980,53748307,17039084,212356353,465585492,1000000000,432504900,163822803,536557633,1000000000,126420815,531758400,444889731,146408718,249203398,164869758,43388596,173912472,1000000000,723547226,4521054,321985067,266015350,0,51749564,9547127,602028504,77202047,63843604,1000000000,729212382,123504406,219556450,21952537,740006855,14500197,251906239,9696562,100552366,196531382,82635313,6607837,12640954,174704301,1000000000,235716081,327766588,339570523,1000000000,1000000000,325848909,36394118,246282227,78796336,16918573,857211450,306794602,323008932,86172237,10401053,97378425,507186866,21804187,3879548,95563884,13133484,306150150,105971290,1000000000,82396440,224469578,9411851,239899845,350421407,528294140,286254808,1000000000,47862973,264235817,3727942,172794805,27865439,57747,3762699,220683632,70769982,209929767,33435507,1000000000,350610168,243186341,274903956,81439515,1000000000,1000000000,96861775,1856281,538768833,224229295,19026165,511204505,294984,290717641,589260293,266621400,32019018,1177691,158585221,128955673,9597897,88059101,34216159,1000000000,56719613,504764067,129047470,534080777,127783188,27121855,96466406,20957038,264884849,1000000000,63633918,15157569,13186252,8544968,214511621,113559543,118031976,174053000,134281059,129932268,1000000000,156461996,83581534,72348543,611408191,271708250,6738528,2033931,342012643,40903660,336974246,3044510,255112679,158181585,209118532,216525557,80556495,352738565,194146060,766070273,616769871,310987437,491433111,159325494,243532615,66029129,1000000000,1000000000,454857363,103051900,281048564,1000000000,45834525,668727810,15822535,249044573,122717278,272094666,114485618,59910311,1000000000,8908844,1000000000,61851480,128078150,282225816,40381001,23348581,1000000000,344174735,1000000000,260123123,1000000000,64946234,284191,1000000000,9714544,261613014,54120260,64465276,181922228,18756825,14028284,107246628,378189966,598469,294146693,1660106,72120946,102890159,269127689,189735896,1000000000,141498887,1000000000,11436640,454012763,32950838,70754067,9175535,319759949,332679029,132791575,321013295,85808350,1000000000,29626361,85168146,303495308,203360975,802961457,209919544,2276909,290902866,1000000000,88663753,55289267,35866736,42704945,186233956,134007257,78223020,368808696,199607910,82757643,68678065,381738199,150680685,108909710,159408278,317126015,981753303,159958520,19315777,1000000000,309967294,1000000000,1000000000,116615165,59915514,5381173,218235510,93197920,7393986,14426553,107588718,169484420,216825909,15072853,20963033,63983926,139069273,7265320,219879740,330383849,327466,76646506,19817557,110111425,83340476,135293843,406544995,65647610,75764281,137048479,611963336,169991423,1000000000,1000000000,998066617,33289664,14355940,46654361,42999136,76686420,266346189,6781578,112364015,320790397,1858250,133177280,27817166,90382554,143348712,1000000000,1000000000,138098254,122813910,289835064,1000000000,12807553,111093867,44544088,1000000000,407729528,6253822,4648214,255354049,152054916,828508086,140988096,272134726,1000000000,160003009,1000000000,178146974,297732885,7229389,1000000000,4844665,137704406,120696507,50745640,293012974,538910523,95427353,372553762,121083416,1000000000,1000000000,119806476,366966540,134507866,443747634,114926673,396790303,98817482,266178399,264998970,554046986,219243548,183675215,788607489,315318213,98279432,75532350,537762975,4222463,1355502,143324695,118484470,152991657,65269658,154010746,37649326,19397416,28989993,301169245,19043446,1000000000,589899521,286682461,92507091,173390599,125098777,8947806,16809869,432218112,96304534,394563045,194239308,178364076,1000000000,176156387,70064291,686624,96386129,1000000000,295424989,46974760,60655068,547171,214089856,371299509,352344864,100839249,33033395,19891784,542463748,36541711,39079369,1000000000,35321466,26858431,375644776,1000000000,1000000000,227516408,215611279,939720748,181419634,129668835,528569435,1000000000,101103365,870330730,1000000000,1000000000,684183404,990848841,120042271,383495905,84343426,193113995,142579771,191068295,190965543,96605189,640387745,182892307,1000000000,110020509,846371236,344314768,468182058,71977674,379070182,2058804,165033257,16177414,52299863,204410729,198879625,76665263,258789768,55740721,109894565,153316729,1195938,885832648,3201370,929687390,285222837,41681235,554215454,829990594,161942194,1000000000,57606906,612435536,83594379,152820560,80002817,187038410,27914689,192677054,580379641,126441256,1000000000,134278403,199829537,7837646,481230489,26506290,555766163,66542214,347901995,157671832,336393254,150719858,118364257,352862837,641924842,250627149,342347743,96608647,150566109,147828910,206512160,71342585,512189316,308895262,127914691,80599407,899580112,54804270,71897733,92966887,602408385,11749969,197815383,562430258,89328165,20479593,5897218,347810962,282056565,1000000000,196995071,1000000000,321986074,1000000000,9487597,70143766,183373461,326979869,71726845,8389594,239098874,1502069,1791226,1000000000,170517116,358882817,72728587,250251599,1000000000,17259576,78773469,395216749,657944975,207195113,306875184,12309082,394714787,17016477,411520925,164337853,146818179,1000000000,1000000000,47895287,52413307,575657022,2113867,139189024,1000000000,284291368,158474011,301056288,45226374,161024735,181104244,76124672,116698855,5680579,23334451,81449557,498602916,199670342,239357022,220549164,257006976,136329661,353841341,214765380,161439122,22421982,1000000000,2428027,4265958,13671053,602611134,1000000000,44118279,59934377,726312070,210209271,375856094,1000000000,322424913,11284786,77275587,425874907,33322673,345288537,19346477,1000000000,23329686,8720594,443481396,388949083,268458270,172952254,37163680,838605,34625455,546530,43779758,521548712,120131750,36434109,76741434,288759988,1687011,40811936,471715101,88640808,50663466,409597442,191254116,157260403,2303201,237391689,1000000000,24231213,36077104,99707689,254092391,1000000000,76816912,350140230,124381248,45150292,1000000000,146525419,98104972,67666810,1013828,277645877,1000000000,8873154,119291807,996564523,204329954,48798834,69019535,1000000000,729094774,202637987,5520823,857215786,130342626,389875029,3466953,42169297,316763394,115875548,77937400,5852867,311739306,303952051,145037295,53366552,53137296,207842106,364745453,108259823,36143509,27268981,70745132,29763971,83398621,337439942,635222925,194781364,91913330,192631871,1000000000,188078977,236453736,13812151,381785548,133737939,16959219,461834975,236372549,149478359,753833274,137022630,13959033,473921658,136834346,74293653,3500750,479124157,68318715,285139821,153406442,21392209,614650172,379031374,36174189,148231561,731274190,21380838,298557161,183479352,81003844,47780920,100051997,3584626,69069213,125308870,210689219,25409171,77987816,199912,885764464,68774610,22080033,22721169,153184575,51932396,30820635,489160305,45239848,9758413,130498403,73321973,1000000000,218884329,84268215,384275911,502802558,251157657,365647273,2794559,494531229,411674724,1000000000,176767867,644201844,341487445,26149717,35329374,232400267,1000000000,524466467,114324875,105502556,190145993,48720553,253006094,3403631,333768106,683906785,318564813,738531440,849066862,164252212,418981400,45888800,296473996,167719021,176939588,471837520,221794930,272707580,733314001,39264887,1000000000,193838527,177554200,463502294,117313457,222616573,239534614,564017456,1000000000,708165821,149018496,590221810,274575215,321034105,380395207,949182077,156281288,57250690,759397014,10217292,674956481,172999549,806589331,81138,344251689,156695247,242938499,22309982,12327474,40290451,1000000000,189886804,328357558,189278542,241095927,37123781,113610453,146839777,62710995,55097236,417922093,32629080,436581941,304725154,87488173,42114110,1000000000,14882919,358702188,75720198,104395961,106039178,2034952,138639320,235879381,81553763,65472300,359879924,1000000000,103515898,263764319,30124241,227879046,67500757,28985225,469554348,24950424,40705004,161322610,121174579,783063487,51811516,62779925,102550655,49404942,333967513,189735240,419830677,1000000000,60404074,1000000000,546924775,23765606,9974994,310579639,709429662,1000000000,533774002,1000000000,794015471,17095496,24686302,146473124,79471524,576717297,1000000000,93546930,201157718,1000000000,10481959,17628886,83887586,617402212,116175758,485783917,10099804,115753437,213881525,181950954,457112997,1000000000,15732884,132204411,8560032,279605350,1875816,1000000000,6779479,382898064,269782881,1000000000,26810377,237650830,73703298,6160142,93810300,8662328,226930106,663689403,186317198,126330719,9424334,16431909,132463837,872920257,311714423,174028224,1000000000,1000000000,22880319,536581038,412844741,526795886,184219108,215566609,158672834,75928323,353643223,160981872,598177470,31388579,1000000000,232403499,347990909,2971045,42375135,91851564,4175433,157483751,4001753,266660328,228976137,256564441,249377376,114867981,26334781,12484486,107570446,860007606,47638157,703099395,36073690,41989795,900474182,69329043,135278967,273764000,1000000000,240258976,120580621,584951791,876596835,271430869,7651923,1000000000,700104009,970690447,504698016,73701427,47912480,932103,220219303,1000000000,960043663,50918555,216724109,145965805,74162571,389106160,257783585,278171655,2832812,305960889,33030036,74573684,36290495,1000000000,162442128,305808997,233458819,577188728,98665431,50739653,34092334,141593292,997248465,578467156,401810050,54646308,132448559,132846984,223461451,225618459,310363620,368205233,210947665,63876552,223097344,433439029,751755499,157152783,321363845,939015304,1000000000,190054730,251189108,24372390,42504158,199382828,42517513,117623606,290336607,66267570,46290380,374379689,472026,83106619,261381858,430732906,693585780,94276257,253845633,63228792,22856021,25171840,86389770,643854275,1000000000,87043745,283058537,37931172,17886313,457604439,310161753,185972873,68684087,3756417,535504502,37482355,1000000000,15549822,101383507,92940178,581708681,346608434,378633933,14104989,935603156,8651320,334225249,2413510,1000000000,4286293,198302090,217566502,461626541,64612181,1000000000,606649133,22029145,3153931,18152416,71269877,18571599,51578602,673571020,10827500,62279107,253239879,967894381,59583272,1000000000,414415691,1000000000,12808962,20891071,82365908,1000000000,180330116,1000000000,287217305,214948010,203574307,58413203,438641005,68869103,66311639,553444864,92551747,105317834,338413735,255261557,20925980,25677595,1000000000,12956939,83118852,530676927,62271682,262941436,313260956,129844536,92545508,940583169,111221831,60824022,426433115,1000000000,16669830,227936912,248447694,839552790,1000000000,491036628,636440539,212345808,378680270,33899256,197727002,18247527,48351896,442084727,101918098,827413234,138263951,59172654,629621157,43768811,17074301,729202474,1000000000,1000000000,169064363,124076018,6846131,270978642,126720549,43080865,8779464,3681056,33309502,39955332,91712705,651495521,40552659,814985233,75083469,1000000000,4719225,132329314,114251473,337794181,45557143,268087666,50329042,1000000000,514459217,202117337,65497820,308030859,39198584,101738536,325512187,50190776,685099624,169279019,42821977,506580343,80244728,717216913,1621315,75060944,420001198,89172548,84517559,180349415,37576180,179562026,352318178,61123891,433653411,81839298,206883355,81402716,234056942,155050987,79796153,429524972,87831595,909841976,253452054,168888588,46992,192880523,374822116,71467856,66140181,761946,61503654,6285781,93136792,154216130,10526535,294351375,92148347,189385668,230603161,1000000000,439911168,116832250,54305226,51423632,1000000000,176145108,45900580,461207232,144331974,153872207,1000000000,87498097,225236795,1000000000,16641817,811517302,155689244,7255960,83644725,86010342,353689915,275981298,139234709,8499853,592930919,136256402,72100357,39517676,41727949,1000000000,48509408,133229936,23216072,211440619,112941043,121378101,54151841,223641083,548973995,435550218,254422725,10769883,3945735,1000000000,28645345,3115781,5644348,275223513,1000000000,190732880,269478420,65002395,331448245,98710582,111249876,525047808,51064791,4386345,31239495,62095219,22062637,63836547,235786829,5428096,496128330,6901616,60007155,146924474,14679608,262832512,1000000000,12855317,76650005,339290941,93428046,338984420,90135893,4864325,43300945,285627983,1000000000,330051305,5166050,51805919,1000000000,252962839,88484474,79989675,152226616,45254622,624033158,245591468,386285598,1000000000,7201193,135224374,103845650,5814012,168916172,419695460,329680969,9079635,34148318,288061469,170761486,312315878,81638460,194879511,202287848,49647278,127135314,267755343,100300359,178649221,248355457,262931991,671311269,25715597,197999649,53584160,1000000000,147777116,4284132,115754102,689315522,45286852,1000000000,39303398,33984445,199840351,40407786,1000000000,216098071,154793567,52490730,50905471,9381934,1000000000,26898640,513389985,49208346,10988242,157157018,94950052,381809249,355807697,373755018,55712188,113400613,72173248,3439396,42592770,825547927,635272301,298971655,360963141,1000000000,96857884,109178802,55230590,2273144,44121830,1000000000,79022824,181593010,152980704,65862039,113932856,196044756,1000000000,64566760,1000000000,704392065,294910264,116809140,385590482,480640247,1000000000,746115690,19008007,8956332,36888255,122788446,36779488,619753890,604654228,202035566,51610379,1000000000,77352867,120736202,1000000000,135392984,75451686,323571072,233977717,188963289,566410672,184046720,37399025,98576961,301139923,24094650,366267910,495774451,1000000000,118848004,18416199,24264464,157541888,261891148,162337061,240840468,467332249,157857810,60064740,11161405,315049649,1000000000,63459748,215186801,656407534,220575984,1000000000,12156362,21940592,847698545,107431557,1000000000,86231337,18598475,8141775,1000000000,624114475,175902309,125897773,61802421,72205360,87617091,27389581,162671053,256163356,176934588,101369499,367642598,248044460,262603906,355356463,6294926,458913397,1580127,100108878,57304647,283213956,448807396,17578495,1000000000,321314420,17699972,215111458,127256526,1183969,75178455,51332815,16540738,133281881,1000000000,7107712,99959074,895408132,548872060,289688508,362752111,394706521,339183527,478999732,169833474,144352803,1000000000,1000000000,147425728,20224271,131456375,48114475,287926855,73481014,22772776,151002412,68796354,21798709,72608439,67759694,228132967,210565652,129470297,72401759,359690400,24806660,43691517,126115562,232355195,1000000000,61515113,210179656,31747520,321013737,27899502,428812394,67046402,49549587,910595893,357902552,81799003,99174040,244038141,106169043,415724526,656976433,110708876,337225793,55101775,368402376,93789119,77297842,177743757,24296692,166992440,169948190,174773351,319198005,243311597,518894490,306198376,417534838,1000000000,93213168,50591879,543674565,1000000000,592959117,220488637,723208478,435263281,338219115,166059970,119779660,9325421,149069546,547050736,118638546,246184690,4645403,7651510,237690152,39572766,1000000000,271003032,381393018,116135110,1000000000,877653197,349107212,555284172,675362947,307711160,452449502,493621662,43441298,56860684,996949265,297226046,396323015,917467957,1000000000,1000000000,15003635,6797841,523368741,11898388,355003307,24643380,74413002,6795865,379921214,21838482,69270710,130653625,122784474,1820749,886922676,19794232,56860576,281528139,86123643,233069610,341477047,197021865,7682391,482624046,60470405,1736301,1000000000,13566141,324798105,58100337,82303182,643899872,2033348,656471052,137447818,102041818,121859842,243624498,7446026,114847939,132260938,156878983,141126593,102500081,539773167,9804102,13571395,524994612,309409400,46631466,103981,87422075,52182766,126709810,184317840,916398802,47526191,86570452,362822887,132140870,177774815,25262960,104062958,1000000000,220646262,272735106,213745637,6850592,2069173,1000000000,569274297,1000000000,230343062,36514861,160553519,261936859,1000000000,160166570,734304583,788115682,1000000000,775583443,14520330,151970426,257063889,1000000000,1000000000,985547334,48084178,200606082,47587300,163186659,170060851,39128743,313321020,90268075,221931381,290845718,167739262,64148296,1000000000,1000000000,22341870,17158634,219569329,1000000000,1000000000,47111428,17946818,148935179,50336837,105200,376736345,23089977,1000000000,747404715,82990649,338730434,423174843,295307486,25923359,42866001,52425808,184049683,119446289,27691153,41391292,431056019,167432809,125733251,3117901,178107400,543319,373011368,671293987,42953556,196055746,106638238,75138339,17725,384907508,1000000000,319120247,12188311,245430432,321739679,2357429,37543575,4496689,1000000000,378817205,855184311,1000000000,112411227,485449565,318894847,595906741,1000000000,137654628,51105468,479617867,38521180,353989435,59617005,768900692,1000000000,385264307,40582615,806266307,186703301,190988282,985041866,334765357,373647883,113420623,118462003,11015483,228896967,171871664,195450880,3519318,68511760,906510101,6509716,313383219,34071200,32612649,86173289,691199301,859361421,89946436,548638215,184525642,164634941,73508635,648278054,703465759,307917311,191915633,1000000000,139340659,150485393,240892763,1000000000,817100551,1000000000,12993638,125281346,1000000000,7843467,1000000000,150020116,190930145,114279331,31541114,195376066,675025706,8520153,277489918,109810429,102630164,97792335,45745973,149714900,273108803,800512800,396111,446232867,337771244,209861292,1000000000,843848228,77594385,164178808,34266837,357098785,230783272,165582020,100677974,229535363,5227421,29010675,927051237,851135998,264946818,427797211,24489791,543660734,42711101,357353643,532181206,115462692,235802832,15199253,337030868,1000000000,302585207,556877935,14478098,78573800,50289514,89646671,313520809,92877106,166237604,359734408,478022185,163152966,64810415,50700715,374346545,417713569,29677968,266855078,377634160,129812925,321748030,351101539,6904129,107682030,92894265,60992477,2592104,1000000000,173791848,234523610,493661118,311490271,130101090,272469972,475475361,158050718,140006441,61893305,602186080,4193848,305205214,349162522,209551763,278762652,28351403,33696252,52718005,182489044,258899532,864801158,136226640,187418855,449126133,1000000000,488669532,62575439,142511386,57165959,82912397,85184063,392596846,16840292,1000000000,182781267,63900042,231011976,328866145,1000000000,413882474,336617632,1000000000,164676921,550376632,523677314,41024638,60345122,1000000000,520666331,569323829,21985912,647396,546791740,863528800,1000000000,175237158,188981090,50167678,445789,950688451,106117422,106300863,1098117,306569733,449255282,237608723,346942561,2540332,8166212,196731692,968013423,168965660,2275223,10823498,601884638,159671487,13768291,179279970,47505942,398946188,64820737,90581800,390081555,343998246,18361636,45847666,45805063,761369920,286543029,25077714,1000000000,117504709,225742138,26019030,79738096,178781257,257445269,14947080,433774365,38295595,66791291,243243595,152428731,213049349,1000000000,33178940,128769250,456250295,77860527,509160814,32290212,35734120,96928583,326721276,190954747,1000000000,34664433,387012349,313667210,403825816,36011568,133503132,64966258,441628994,7308842,106600266,7432209,334563958,1031646,311401446,37474173,114282406,907451706,41369128,48445775,162642566,8609127,1000000000,202683487,94051127,1000000000,1647201,92970886,405317458,103276651,593896978,129524384,23386826,156707351,210364422,61383270,19528594,53938179,37078176,228932940,13986470,567723615,160450117,241131951,92072552,5363042,36363096,64023256,7001581,374675472,1000000000,91120872,332591521,85665441,111788566,14614335,331256083,269048716,206614695,14247262,345092874,53162320,47874434,1000000000,452316279,236330970,110886072,129347615,320133065,13140850,90967796,96066490,156128900,357811902,675424,170337620,223154728,55660891,253596490,430944898,10155697,137977262,389281283,565034463,1000000000,732306871,150396048,150654393,271096247,358092136,307492827,311146204,219559603,107457161,165524413,19361771,26290396,9524656,189358272,42237249,80699094,643158277,1000000000,8471920,421835129,221459027,122523481,715116515,130695928,74707363,255442375,546391253,56681771,107201253,4351243,139308697,582438012,138065516,32429969,1000000000,53516057,63457434,251665536,510031,26142157,104609422,654891432,37513766,31838745,131750893,20638791,170105696,163956604,160178231,1000000000,753912483,82007711,17171347,299608500,150615712,20125291,574836462,1000000000,266000033,628250418,621647824,344512584,45640452,971718,130302339,73619310,628798960,356517747,1000000000,270052863,237524018,138530158,60378709,47537129,1000000000,77360790,17099480,49961368,1426968,462332534,143629093,829521758,927664930,1000000000,29933193,58389899,142361465,185011977,209939694,215390055,32295946,26843134,4142869,208515916,650009566,688736359,273977234,232990698,199072,341424814,80732157,89947259,1000000000,220553644,3953248,250816355,421516696,253103118,409543738,90900713,20198880,33993428,103834672,438073815,111651493,128221901,32121458,1000000000,324166784,175915157,1000000000,250315580,37806513,108688878,143346362,1000000000,1000000000,200796186,365002243,149293826,172945127,471629676,70050553,880419798,373473055,81215588,648058706,1000000000,846871,1000000000,169443433,28036899,1000000000,659327895,35798351,1000000000,234021839,381594385,73392800,18600670,105966021,162995133,470766747,3737306,188464403,88818633,7172511,1000000000,1000000000,377829828,140390427,381711095,59378768,232845551,388785617,83796689,992338011,31333600,70116274,1000000000,444786145,1000000000,438882285,400367537,109489025,1000000000,115765139,104706378,81791892,395850959,190124876,1000000000,175233271,4067181,538244991,725405521,1000000000,220209776,949725416,373007557,1000000000,140512499,66353018,222430494,411706423,90085992,554880673,1000000000,207856247,78845365,132489715,162600520,29263664,205945968,97877862,41926907,140369861,95480708,40352524,122879345,26498257,138312910,880038938,88140648,225620555,190318343,100471991,64740124,287838895,34044853,66001022,922861,111477979,301480749,369337574,10745454,277123529,97590732,193894694,542046540,305219343,75427605,558386534,403375715,66620699,29746454,981571390,821819191,1000000000,580998,88666256,152202185,470075723,326053263,49239308,931671020,391903677,458626428,422625232,230964710,208507178,135561318,164609729,175622897,182115094,15966168,184524949,17787841,1000000000,149113893,41958513,95312200,43839394,95517294,26401180,377294845,109637196,52347194,1000000000,85772537,60709045,149417647,1000000000,1000000000,187244582,103930886,145026205,26741121,617259758,211301071,382379008,285921741,266312162,1000000000,701011038,480119175,689764114,162506266,248872369,179481700,297437942,199095291,106199422,514128363,96884597,95588373,261633045,399351711,29482748,130942329,596865053,320024,10639155,490077238,1000000000,191101498,826004802,361450923,619487778,342358682,8524210,1000000000,1000000000,287448136,97056849,8347231,223261777,1000000000,40803296,457070144,158375826,7075254,245294856,648216487,309598184,659164092,60866088,381578945,15057830,24426667,419250850,359075,265544049,193225138,98941970,1000000000,76521413,29311766,494146284,406479370,65434648,640127776,68174483,12642855,311031018,129952024,138598164,1000000000,188047106,391789718,11132286,625873911,234242824,54510819,140437335,336204899,527068856,13041418,52037706,53694081,226651943,35715646,174777577,35529896,2851271,85698612,848946567,360404826,16465447,256438667,80420010,17830654,129582294,48548672,1000000000,37988071,4413955,41181697,22408003,203953121,1000000000,10214490,269921747,215733109,1000000000,163638940,20412597,191620520,34476297,158749611,535585849,211671482,70925039,935558058,222082578,591592789,45484710,6138736,94902283,94577413,153001201,187149911,98652893,281784088,87095761,191520337,680760,1000000000,429198366,864039503,683778417,44358148,59623620,289996304,755976844,505702824,721297946,124248806,184072776,1000000000,66780166,3356413,142877555,389527237,135792924,143408864,444090997,161643016,1000000000,153503906,175246722,338232959,97730837,424296098,65220876,604138505,1000000000,1000000000,366716828,5919280,122005221,279632775,63328586,235695957,453320706,83367365,876019117,292800776,1000000000,85118504,1000000000,730263312,293732274,26942532,40199908,36894705,152205068,105395781,156495145,28640465,1000000000,47847368,297411589,336373186,4704310,305954901,24012324,100615397,21242714,23874766,159541867,1000000000,135148436,1000000000,346972801,42793921,8628165,48529253,24302927,1000000000,1000000000,280803298,51163121,618264730,255277857,1000000000,11929788,15136473,589827962,50853894,1288712,91068590,649874573,37301163,3003701,848029848,1000000000,32758344,288886234,98147357,11637723,236927369,21890472,4300773,123713754,1000000000,806956815,60649070,455500804,727887752,7553523,138197305,1000000000,211582823,501711751,385088836,190401815,381354224,193296171,1000000000,1000000000,77775082,43028788,31978054,53365241,4024649,480704567,388764743,385836668,172918342,107440484,124702057,98329926,87792770,1000000000,307011215,240106261,664470090,170242917,48589597,260630788,24223876,154192,488334407,132298728,111839618,91422912,115499826,129387457,434918044,2618203,27869300,79074909,945422583,24936595,84654117,38294087,1000000000,222010984,689548486,1000000000,325752193,748465727,400413732,120557259,697770623,780578388,151266723,1000000000,211664938,18900394,1000000000,102394449,328827158,165691739,409676073,140972756,1000000000,1000000000,134251527,101974674,168034928,36455997,173115815,8831467,404211445,799472571,83912220,435944332,22167381,25490882,90231010,65229254,81027762,82563934,342328815,66497992,342567768,440627,19532707,228898349,1000000000,702990169,792766177,11045929,46680155,74303828,969125538,231489528,63224256,322704244,562753961,708398779,151250399,154616416,18171397,30113842,66839321,237995923,24543299,779126701,1000000000,124919506,43730932,6025558,309085997,34522280,176562104,846635780,840008221,188906266,451536955,21285436,304022187,219140516,1000000000,726265922,684463982,24856729,7652482,867046519,304482600,23472228,182839487,17190695,295019637,254666306,40659735,30464874,299422140,1000000000,1000000000,425820120,223095503,164283664,4527175,674637639,768027550,85842358,360588227,185978514,242926174,52395280,1000000000,121968993,112572048,168571781,149932265,1000000000,92691413,1000000000,781534848,234564985,23028917,178850842,210174605,850598572,61783250,1000000000,1000000000,1922476,467094389,33698617,509862328,743287980,1000000000,276822248,218020786,283734099,72895797,905437153,394758533,190155919,409733,38551564,106354931,70795475,102525954,260477610,257319053,16779564,62848578,215357036,16858026,566688894,247459813,498155,197362897,307182825,31813449,623895919,28487999,222760496,39713889,130569244,98815714,100558176,61704987,87197025,92193983,181740542,11993881,1158913,298780011,197718723,248569335,36169183,73609387,1000000000,185278774,56418985,48061512,1260690,122093002,99000204,234682376,55430328,6693270,211736516,1000000000,96732048,1000000000,182052492,791659621,9543603,67509048,98443929,367412124,1000000000,123123355,57918314,694887603,1000000000,602248370,130647147,170814526,103527789,271668991,82434526,96793178,15818449,1000000000,29008278,803636707,281043213,114985541,249870501,1065878,116651360,43703129,215125148,319739774,135379743,346780279,9240344,1000000000,610321,473723109,193554378,542802755,780296183,107842640,1000000000,262230144,35106391,557655934,9368401,75261259,2536222,40644952,761707873,716646600,1000000000,49491777,38851686,16787148,1000000000,6656862,16244449,111399316,530804583,5862059,168455011,144071009,24902239,46133315,121774122,520568017,42215606,175524865,520223776,26246482,72395235,416485211,53997487,1000000000,68434923,1000000000,419840653,485905350,105296416,2380381,263580773,13892576,12324776,226672199,583307515,40010548,370274100,25307409,1000000000,15421003,23057791,356213627,549353866,60836526,934151936,765316980,147481942,144972156,426159848,875893170,324326930,16315358,674271474,20247721,1284412,262017816,123589824,41399866,72699035,60266458,163021190,175377015,230645917,1000000000,352745290,266330168,1000000000,26780146,53352795,61475767,1272825,952057998,252544083,1000000000,163984834,220946040,87537499,216605821,450243103,0,410302222,51983064,166153830,1000000000,104489570,283180979,228862192,432286489,58757468,151953013,171983873,156193293,137348703,818342010,1000000000,1000000000,299450498,359159283,148237459,18695590,71900603,119621950,1000000000,167590677,385481086,366978156,1000000000,24498962,1000000000,315957029,1089980,179032291,195402384,7603310,62254010,1000000000,1000000000,422021739,885177299,327587998,11942016,135860446,9010724,143142616,106740479,10839824,71531317,221837210,1000000000,155677043,43525518,1000000000,112068273,102887626,312350732,150728134,79747516,211943761,10045815,81305865,19758663,314677146,21079006,32434952,1000000000,61378078,128705586,141385229,3854636,18497857,645913001,55553745,1000000000,241669361,371639795,567585702,189136908,56897919,167821817,179040000,607819551,57866964,1000000000,149462127,34894610,120384205,72322312,49422045,33425873,228969361,898062817,87085007,142410479,1000000000,227823979,60501240,538763041,214192103,297290536,68753213,382016031,37685888,152402476,185616648,10718290,87270573,136449130,38781040,35271747,1049743,107781727,83731161,46782643,88289670,192947261,25000649,302774339,5593787,166897145,596773221,42163032,1000000000,333445862,138603026,1000000000,166369372,9555279,195021850,40169183,1842225,182396519,122642539,188125440,99733762,154348212,67988379,73879297,1000000000,121633319,137191191,32382502,1412052,199321015,146890875,32843735,40082543,12598003,339178715,162013731,46912820,6813035,80169046,258561137,2845452,199386376,478008091,26177477,95118485,465976672,316487136,444560737,292706325,83537231,115390448,318717451,183028598,1000000000,77489046,13744770,552844606,85234250,30527586,164437874,1000000000,11085904,1000000000,163214114,65191337,104342266,263541235,27517912,34389240,230442523,395881446,281730791,333061311,211655764,1000000000,111403474,13317145,283605183,1000000000,272149072,180255099,29956780,73727325,1000000000,13510718,146005180,24136510,107315380,34920194,345700034,565834845,82994638,258801325,190533003,112630544,1000000000,69693761,227067863,23968895,424097574,13200997,261162006,503659416,31199965,39819088,6620053,1582893,192146348,136905379,1000000000,153931758,24027578,9112509,220867996,41439826,1643582,820368233,559966093,259890286,252765048,258300784,284774086,119743617,642690026,44362932,76839093,100763536,170416753,463772786,799635650,84597405,151741915,1000000000,361120689,3643342,5628787,216214080,407622891,515206702,13687772,1000000000,49826218,17419395,211944435,263056474,76969998,90426689,12251443,4430627,180061135,43946338,80066731,29225717,1000000000,399623960,11468481,51940209,350831481,279392894,49770141,998719382,236045680,436026949,131744103,16050995,390382160,1493238,166462684,157694622,38153072,281629965,622566269,9574576,314483033,137412942,806268649,447158021,1000000000,118844729,7964166,988618773,204989994,59259671,50036763,253027792,13666085,53877392,91450275,564118358,765089141,1000000000,239200152,588190422,162773174,8500677,53947642,52543326,260713228,350628675,7549136,1000000000,57323720,1000000000,247977999,1000000000,130609505,496860987,429457294,13940261,276946756,44646924,378739566,55143771,816207589,26931866,144921819,78872927,197463698,15468506,366616390,234560071,56922595,373479955,16490880,78097262,8607333,94652206,297119221,94116013,10675624,175894757,57049855,18047821,19812654,16172518,7156353,668189305,289638189,255824385,275464181,658516477,1000000000,171805753,13357554,1000000000,132966924,1575049,229232803,60423428,69493671,70914980,686123712,40318527,98512827,856704145,130085411,120114459,872362839,31475592,899297380,1000000000,920323033,1000000000,236859873,716013525,152744439,745054457,799078472,232190743,9447394,498408350,5505761,316719702,161097212,1083590,755417468,1000000000,132783091,104603243,613191526,81009340,678082078,1000000000,146651916,1000000000,1000000000,129982283,405788641,975058376,128882955,332161609,768789043,163187263,502745382,1000000000,1000000000,98108610,86182996,561913631,179695514,1000000000,55044061,133649167,6633632,48185437,300153188,500175437,352592785,874049013,10100457,273118214,1000000000,108563829,281855263,99335642,12883318,249771208,114052989,18454367,18000378,57393624,268190337,451301420,472396148,276359733,367371842,62450214,39563257,186194795,34229508,106144232,140219782,56175432,1000000000,969694060,161264310,129119309,103547840,1000000000,1000000000,5557068,268656037,773511756,64923460,51791337,167395508,360001871,49909788,1000000000,182310701,136042667,499408503,391990372,372028419,29598468,54285903,108152459,662388199,150701761,287131327,1000000000,59408078,386893141,152264481,15086402,13139994,2732788,20493923,520074628,47194741,151153363,3115951,30785213,24546436,1000000000,468042174,278240003,141562269,385623564,109208534,250297099,753803402,143716288,831845009,35330112,321089630,41389343,286293032,7222898,611683488,459058138,21675200,356670286,330533938,209590325,187972565,106689187,123995563,307603247,785810689,619593368,23936308,4504657,37865553,780162323,140771254,70272089,1000000000,224652737,264473605,111587663,658647761,193371568,505977495,6312191,138984625,328342173,464178898,97369704,269530168,6316153,38601718,138231609,1000000000,94245575,178189304,1000000000,268364135,2077152,168604009,26545579,1000000000,227279999,81757846,102218576,37818641,426138684,58913666,175854629,14069217,409028925,59225901,366832910,83761401,1000000000,76419231,3706396,287209830,137686202,464641398,658296421,314179227,271168201,301465060,66207897,83018926,1000000000,1000000000,70472896,837431441,304669220,1000000000,256347261,28812363,126683630,332699534,48675183,62232807,59465528,208039306,1000000000,43090774,26624067,785301178,19724740,534429421,387874306,152497647,402129783,65726934,10318088,246016611,433653577,108396654,8534437,75353131,29976075,80589167,31215071,18446606,300434986,606181967,1000000000,123713072,5847457,1000000000,28349715,177820036,133851049,103382745,58026932,31550593,14775328,1822325,257466380,719305319,1000000000,3210471,255410928,1000000000,49525433,504490350,1086106,1000000000,76820838,150749907,84020280,50354617,340052077,66223261,435416910,28919890,204816074,52835902,1000000000,70951475,54930142,165917468,1000000000,725536834,94627081,254799274,440556473,75015312,336645916,831244430,247037230,349248396,115177979,54375665,9283425,53858433,166013373,2581702,4542779,1000000000,1000000000,314799387,971778360,169213265,753961,76273462,1000000000,163483106,54678254,147117288,1000000000,5846458,106318679,66366935,69167302,196005269,379204138,54219171,173580083,391483315,235781016,408027935,29482088,43514691,391071434,131840441,224675370,96470149,1000000000,416623886,194544828,1000000000,52823007,188055028,344087194,368330457,296556483,2358671,1000000000,74628472,1000000000,356552777,310751510,453415574,125925790,1000000000,54872049,565448799,527509681,421686033,1000000000,1000000000,16302111,515029720,184782942,1000000000,214473511,1000000000,60550003,174876736,63882095,103402677,122116069,1000000000,52417365,521472845,171205501,189145120,35703719,280391880,1000000000,60739589,48225378,192306365,220956505,253278387,48391466,11255380,125706531,112059987,583502292,14330829,475217252,294727578,177102517,244011945,1000000000,138478636,437866398,101862688,141153399,207473196,39810935,55501783,252056171,43215212,436070109,58407284,395575298,309082541,91075635,395205426,81324489,110984770,590232,59730826,45167098,253843748,26559765,99073652,251772493,116053270,11075823,504037065,25882880,1000000000,1000000000,332311286,263170409,114852167,86999176,888744572,53726372,558068568,216450090,1000000000,506981401,26761895,108786410,12206881,1000000000,178721705,147160340,97803073,19916554,174913183,1000000000,1000000000,239258312,131786035,1000000000,61785376,841278994,113837347,5342352,1000000000,692540829,93992993,485117256,1000000000,477607136,2888509,298506479,601634933,819244746,1000000000,24463342,57886998,224308858,97099492,94616582,100748112,1000000000,773813863,1000000000,1000000000,383093718,333845776,257606098,54250431,292197154,175475053,226224562,90307964,1000000000,13835922,1000000000,30092711,416370599,140354030,167478815,312450695,292276585,80786909,1000000000,1000000000,76722960,1000000000,11530345,126238240,95153357,38915049,139367001,149659462,17519300,233321678,7001240,154425653,89378398,193150500,139908405,94089589,186451234,9595465,2660164,3221957,143357723,12674893,66776187,6980626,117652458,64758670,16091244,561085115,21714955,562275385,125873221,60373327,122534933,42373011,115980721,475484431,46679516,76347745,475188371,108564280,1000000000,42874356,55895878,33631006,121500967,177518077,255589625,983332718,22054702,364956437,219819780,1000000000,199726193,377606126,1000000000,1000000000,237125999,214613635,12264412,9335815,33882625,1000000000,211585427,1000000000,14004851,86121602,155906880,19330674,66384589,24972,249233421,1000000000,11271030,140769705,14962762,1000000000,244232492,298525165,306495330,28874762,18509400,17133167,106110059,287227824,1000000000,22750312,6261185,156839625,304009402,870351253,13865203,368124784,178242126,604716257,87398618,10671023,158930800,1000000000,160361457,66789110,137762892,483059255,254329347,661944420,45352757,1000000000,120086714,13229944,152788806,376376482,78848953,2143399,211458627,53624949,283034784,1000000000,412332195,32586958,61469309,723655,493583158,1000000000,534805393,18940858,440790661,1000000000,138286174,873486687,465555114,655189630,694523760,921583938,241994489,119944904,19199084,524102431,110293826,38497325,200440789,65794821,185583086,769909128,419635352,405451542,110550545,833692572,99555677,81834070,142342965,183351665,138211317,10847243,2848813,75826542,1000000000,153761818,88758220,1000000000,572787327,25098794,1000000000,155296636,37676321,455139939,34788730,462210,13371049,15662185,2774261,15673272,28137285,215284005,12661206,64046456,195302806,411671904,74929194,71257938,1000000000,1000000000,265619151,1000000000,181262331,24235233,1000000000,347138833,245137144,385197856,427589875,263307045,97105248,93506493,643821401,316284485,1000000000,138522666,185192705,1000000000,182993575,545108720,869745940,106545257,174052018,204228340,811498883,185089457,5677581,16146701,283988351,909733282,83724016,32689393,64263531,19490407,55854964,745925654,229634064,117293904,246094779,183133246,266866533,17669247,1000000000,191204310,828271696,1000000000,48415774,1000000000,57219475,9187319,175039817,499740343,59048982,160749148,307484380,1050748,803853432,102836935,489892685,29193190,32232678,90872218,304571584,1000000000,307408809,18107779,169181659,53396054,955223952,256027772,246229613,246782678,19853375,7827777,319197965,64255958,1000000000,1592171,25993276,24916619,1000000000,210110618,24457859,1000000000,131619100,37693537,56757078,579797508,74972586,123270473,79905142,175127782,539236,19959579,14293350,494415074,18515513,823279894,4418387,2694151,79553001,67675788,47067068,38659980,189685891,2074066,337230216,226461150,781859929,192019502,296001001,231721695,243061885,120978256,90391904,64206155,298702334,12760969,168175573,23191956,367596426,109438716,50979742,6718712,386793182,328309417,166609822,34607028,278696475,744066910,420887671,99164246,364839713,112877062,1000000000,38791982,221748001,1000000000,12658782,34812209,42178122,78937390,83956930,69208967,230534846,44819690,147194953,62621669,954693234,121138408,20743441,48492791,407093742,208771641,54518442,222613033,258509435,416018342,27523434,70094375,606531118,73572722,297159265,438993172,716139683,1000000000,61147826,256121745,166896344,54473382,17353424,1000000000,223844626,397546090,121961902,217170918,54963566,77364258,6203396,105836304,203779358,190057458,181891926,374150863,536701454,937918847,173176253,196574543,153190633,178145999,1000000000,1000000000,389000598,241721374,4577866,104598298,491541638,85022173,60362038,1000000000,90491978,773129477,80521686,138016083,1000000000,33060697,204710202,99618767,1000000000,39194692,2109585,376698097,591212493,25761994,158672709,561811302,292626927,19593932,676369714,57266123,198257165,808453991,1000000000,832737740,290922021,1000000000,1000000000,7401946,259468574,66162382,95208668,290553,265925385,6170051,211388355,542760633,445562331,501676574,65747942,521686039,448431859,484528040,422138340,182077740,1000000000,745090673,1000000000,41046347,81516108,203976456,91288218,61044750,217307190,15509795,1000000000,331586684,72639616,190696449,142202156,438475434,2882781,13456107,1000000000,30639569,157678875,16134659,1000000000,666551973,75604617,474319643,145016174,242630703,33121914,58208377,187759594,370958388,322846227,128049626,1000000000,447997746,246992078,52915942,609743682,505619932,382144184,15183463,116193342,1000000000,4008351,299689185,784475463,80212612,5487223,483927559,113278484,1000000000,37528720,67793767,169450093,184328961,311286937,177148279,156456585,16476445,384863132,42333470,28152235,1000000000,87146418,3240627,299814314,36942998,254392294,261593223,64087759,376133434,165600596,244422495,128734031,140743614,50894194,23641831,6021915,18089720,226435592,1000000000,220471935,592545284,55913633,187349632,145085600,311698293,307609642,6315934,409671280,941470668,32772162,61427436,180419663,73593365,1000000000,142069524,55189481,180654944,74566846,151308369,709575794,11114783,164067192,22949867,1000000000,297361487,7701937,9764193,64880198,3690,107467064,527850607,273184802,244425755,31077381,58103271,25507588,129296883,344349578,1000000000,243314232,72729553,134641373,107503411,28181064,4562372,10853858,269164524,70631176,248094583,67465193,80128493,80668345,42065877,31466654,165349105,79932344,646023463,11752124,401382544,22806960,303934755,874084,254527686,4681692,101398545,16239822,660351018,143495770,124137268,227765300,28530822,293297735,1000000000,88484293,377761585,230466851,721109165,45009627,202857408,108930416,1000000000,1000000000,1000000000,1000000000,1000000000,52886828,18274775,466806897,19653162,26797869,388659758,91375440,21650699,38810680,68258584,191318830,16536939,32563861,3577387,120240367,113225189,134505479,8506833,60793458,473273309,264695439,207670674,201610999,2267190,81791982,7071267,66318254,7343440,203300949,562787735,198240489,265664976,55909225,206188336,417325620,146465446,144267374,190035874,206895657,734052362,80487008,96240217,29925933,50773685,68986695,18384041,79533108,228543715,910043,116152326,41746600,151166279,34136773,88012225,241901852,44823891,119485032,40402870,209315897,196111470,282553061,600212636,48146429,120691232,156576077,383106026,54554306,103543084,1000000000,873765163,55972908,233110927,424254191,94499813,230659904,28496505,5529758,72360862,1000000000,219539094,23349479,19529304,78967915,197387734,15863917,15454931,63355556,1000000000,269680542,138524126,309118191,361026058,443283469,44715288,1000000000,12354875,189913205,1000000000,342453763,88888145,281527939,171434645,112214309,47240166,212349542,80208596,267140473,99117616,566670950,572295967,70987757,123689827,102786685,37648667,119270296,448054772,630744658,407136996,113523567,2363218,78679705,60590459,275966200,274284934,231555127,30389340,120945801,84013904,16458527,137550523,50694147,255029220,54567234,333660174,41528550,157945388,118941959,149818520,9849713,1000000000,239681627,495989610,59688435,126783672,97499645,5443329,1000000000,220180995,133888772,1000000000,684038053,97354514,1000000000,47898614,451052569,550603814,442473292,902848971,250263917,998695052,121670844,1000000000,67758469,33273050,300193143,476599351,64489101,114856728,1000000000,144616131,170198904,224897152,284140348,445260946,111266851,27145521,35753490,279730908,113117693,275105915,2301659,5396007,219359361,12272214,509070,109333550,468512303,523504240,155703097,181643280,1000000000,1000000000,1000000000,83480286,856605823,66710432,107776466,17785849,1000000000,20036468,55913352,12198824,459728631,1643409,172937951,184380242,1000000000,1000000000,734026778,5355270,78040965,132796014,228724354,322844218,241400552,38235985,136658996,48386030,228749687,308415496,527662811,789531461,46552004,1000000000,271634040,168357529,184132615,1000000000,253267654,232939608,1000000000,1000000000,478456686,208864093,165194558,160024432,422572343,84273600,145935295,116633398,1000000000,216015141,250467767,150060043,1000000000,77641575,110837580,98990367,276003973,80501898,129426613,29989855,51704815,536730319,53961278,56958495,258946047,266590918,38539533,335107674,31323080,75895341,182048624,38303467,24769193,220522098,154164841,157380384,422010015,1000000000,102741791,177368455,13697790,24492304,30534149,442944756,107449399,298418607,139289420,68490165,561416500,47541472,91496931,385642882,1995994,1000000000,450156383,175634752,67673291,259702863,98541246,85737061,89923926,863454061,421834253,423819536,311530267,519692502,622042790,100307662,233783901,190624995,12144346,236243974,30878041,75301134,561515977,1000000000,28226165,87626527,23411551,477718169,268438068,291991565,551155642,239165409,10687300,508994943,442430535,633366,157626266,437754613,260383661,210494264,16907348,285647180,548254931,101206888,333932520,1000000000,112338387,72941814,1000000000,83995106,124839668,239318336,1000000000,541963217,210446103,153172813,444738592,189871085,221937198,528566261,1000000000,547837295,9795814,162256753,1000000000,121274689,1000000000,68255295,197478615,1000000000,211616376,415293292,325505389,69787667,115406018,494449230,962326660,960135694,1000000000,553822199,428865773,413275871,54980186,276527602,110620769,558092867,457526768,343740050,265222175,103385465,164755394,159226165,17535130,1000000000,53305916,667309174,57732876,120294380,517514534,1000000000,41486398,217079916,160583708,44166144,7695668,155958438,112422205,540937,75668904,9433188,1000000000,279820712,1000000000,117156677,450895709,249658257,1000000000,23490789,7242145,164578576,138273946,1000000000,110139816,882365464,595326194,1000000000,296941160,410665,367220986,540317122,377426995,70968724,38238816,1000000000,273254206,246014663,34169637,344711252,1000000000,237208323,205728572,48344953,274043746,155280724,125845751,1000000000,302929420,63022486,147432194,325404790,9053130,26126302,78865885,88940600,287474261,45451644,85594278,579276537,431599431,155571924,24805544,80031622,1000000000,1000000000,222129563,250834297,46037434,512674069,237197704,349898878,165001277,221011659,41849564,61919397,412562339,38847350,79462703,205701581,22086732,77065874,1000000000,292435206,292357986,25271546,6180070,33634686,6655599,30393035,2756660,102123183,5882145,32732173,179462610,85963871,99607620,113644447,24216565,91305111,51209600,144547783,1000000000,53136542,97046435,98644753,66321297,1000000000,403065989,85888820,108301757,4512674,298283704,831639798,1000000000,10616771,151291557,1000000000,1000000000,3193656,157822622,25241447,256068601,231929374,347058721,216126067,596677657,33378600,124969945,759447428,786964651,394361873,199445615,450748045,44685898,33341682,19283559,220491732,3095979,186533550,38190112,1000000000,492149618,190616289,89030451,365619805,87093697,137350470,57429262,74651371,6492635,127167995,1000000000,2521597,446215035,6142194,105282686,3993284,25618414,554129297,1000000000,15568902,27426945,202468229,33002000,1000000000,146403876,846807197,129119557,3017266,299704197,44335022,265379630,79454970,265697088,133385936,34148805,143139165,66365037,34911510,239342057,547167208,623746784,1000000000,93933909,20595250,217346879,47318933,238103044,27679826,11296707,209778105,337438213,766970561,163643541,88000004,73804186,190850394,114766391,162085923,764127685,317238008,3595169,494355585,1000000000,872142,115581214,502963077,159750872,74977196,235249416,253853118,989976718,7051928,43812596,428435345,337794961,13791260,299129456,2023427,244592280,385730907,73619889,1000000000,283254813,1000000000,259506584,909803416,71526069,5251545,130115892,28641062,1415577,220972590,356216594,133740939,198686492,274934997,1000000000,340699,231363337,262146399,249197819,33946839,305476065,62180638,135798739,52149238,30987575,1000000000,368555563,751478809,163840703,334714174,521807638,354811008,223298222,17978225,338852855,346520526,142527780,277525495,124713896,1000000000,285433485,72393495,11084998,1000000000,251290191,1000000000,16448779,60803013,1000000000,53213995,37776211,24212213,62854122,645956073,175058391,153637602,661969427,16726572,62923329,58779919,1000000000,557902692,66359800,1000000000,319268305,44308396,136332625,47574758,593851183,206057665,320061343,53826610,206206519,1000000000,137284031,8258353,920629349,55933204,211728390,58314969,10055450,303403724,42494742,446551250,90679170,44831879,340900736,1000000000,230572401,792948329,206615456,257533800,1000000000,15479499,257886007,212651566,60750410,262292607,14236024,91185623,43640827,123982158,424404155,505871948,172418198,72241200,11177883,438441217,58091748,95809959,964533376,6174324,443195845,968489951,66863462,156124441,1000000000,275634014,1000000000,636489,874334704,216439,11980023,46479515,861540822,1000000000,320362012,25134874,217082044,39788634,244652123,341966114,189765991,719678214,46322443,1000000000,155450752,190479248,450587355,816083768,524570418,49026805,75792020,382079126,124423229,176589856,16963310,155116373,292800039,39754115,77040989,23912175,330439805,166852464,8891818,687015,1000000000,1000000000,304102609,629201543,1000000000,7275721,1000000000,100374677,29951484,64727558,130865401,72464269,150264343,624181282,66146136,792101793,36547566,244430406,245683362,223549,144115027,114633990,12913988,447325169,273913336,31036852,26505688,57394844,4393140,496492215,615709677,9346829,1000000000,292878095,345770158,1827522,138987954,459239011,140549375,269404983,11867013,9117804,495820492,45793617,666581805,13877734,523330491,1000000000,718286,1991767,13057995,33530805,19511670,585825795,1000000000,39753239,53697492,451890806,286273335,206993275,485737106,749304715,1000000000,181268044,1000000000,40133194,84540047,332010844,102883567,194524366,198176346,18454976,86372760,204029593,39896101,294926308,19191640,370433948,279295196,1000000000,149838180,728952522,12040188,406191671,83432248,28853710,955522763,27894992,103193148,362985696,73976791,971154047,39653207,576458822,164039358,12947739,855195558,276891987,1000000000,44148722,298668670,144473376,444366079,49665533,83466939,27167446,1000000000,164315236,490539189,34026766,731627899,66580458,134066884,107090500,377656,145886905,46905949,179456000];